using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("3 4 2");
WillReturn.Add("0 3 -1");
WillReturn.Add("3 0 5");
WillReturn.Add("-1 5 0");
//3
}
else if (InputPattern == "Input2") {
WillReturn.Add("3 10 2");
WillReturn.Add("0 -1 10");
WillReturn.Add("-1 0 1");
WillReturn.Add("10 1 0");
//Infinity
}
else if (InputPattern == "Input3") {
WillReturn.Add("13 777 77");
WillReturn.Add("0 425 886 764 736 -1 692 660 -1 316 424 490 423");
WillReturn.Add("425 0 -1 473 -1 311 -1 -1 903 941 386 521 486");
WillReturn.Add("886 -1 0 605 519 473 775 467 677 769 690 483 501");
WillReturn.Add("764 473 605 0 424 454 474 408 421 530 756 568 685");
WillReturn.Add("736 -1 519 424 0 -1 804 598 911 731 837 459 610");
WillReturn.Add("-1 311 473 454 -1 0 479 613 880 -1 393 875 334");
WillReturn.Add("692 -1 775 474 804 479 0 579 -1 -1 575 985 603");
WillReturn.Add("660 -1 467 408 598 613 579 0 456 378 887 -1 372");
WillReturn.Add("-1 903 677 421 911 880 -1 456 0 859 701 476 370");
WillReturn.Add("316 941 769 530 731 -1 -1 378 859 0 800 870 740");
WillReturn.Add("424 386 690 756 837 393 575 887 701 800 0 -1 304");
WillReturn.Add("490 521 483 568 459 875 985 -1 476 870 -1 0 716");
WillReturn.Add("423 486 501 685 610 334 603 372 370 740 304 716 0");
//42
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long mP;
static long mK;
static long[,] mBanArr;
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
mP = wkArr[1];
mK = wkArr[2];
mBanArr = CreateBanArr(InputList.Skip(1));
// X=P+1の場合、ペア数がK通りならXは無限にある
if (DerivePairCnt(mP + 1) == mK) {
Console.WriteLine("Infinity");
return;
}
// X=1の場合、ペア数は上限
// X=P+1の場合、ペア数は下限
long MaxPairCnt = DerivePairCnt(1);
long MinPairCnt = DerivePairCnt(mP + 1);
if ((MinPairCnt <= mK && mK <= MaxPairCnt) == false) {
Console.WriteLine(0);
return;
}
// 二分法でペア数がK以上になるXの最大値を求める
long Result1 = ExecNibunhou1();
if (DerivePairCnt(Result1) != mK) {
Console.WriteLine(0);
return;
}
// 二分法でペア数がK以下になるXの最小値を求める
long Result2 = ExecNibunhou2();
Console.WriteLine(Result1 - Result2 + 1);
}
// 二分法でペア数がK以上になるXの最大値を求める
static long ExecNibunhou1()
{
long L = 1;
long R = mP + 1;
// 特殊パターンの対応
if (DerivePairCnt(R) >= mK) {
return R;
}
while (L + 1 < R) {
long Mid = (L + R) / 2;
long PairCnt = DerivePairCnt(Mid);
if (PairCnt >= mK) {
L = Mid;
}
else {
R = Mid;
}
}
return L;
}
// 二分法でペア数がK以下になるXの最小値を求める
static long ExecNibunhou2()
{
long L = 1;
long R = mP + 1;
// 特殊パターンの対応
if (DerivePairCnt(L) <= mK) {
return L;
}
while (L + 1 < R) {
long Mid = (L + R) / 2;
long PairCnt = DerivePairCnt(Mid);
if (PairCnt <= mK) {
R = Mid;
}
else {
L = Mid;
}
}
return R;
}
// Xを引数として、P以下なノードペアの数を返す
static long DerivePairCnt(long pX)
{
// ワーシャルフロイド法
long[,] KyoriArr = (long[,])mBanArr.Clone();
long UB = KyoriArr.GetUpperBound(0);
// 初期化処理
for (long I = 0; I <= UB; I++) {
for (long J = 0; J <= UB; J++) {
if (KyoriArr[I, J] == -1) {
KyoriArr[I, J] = pX;
}
}
}
// ワーシャルフロイド法
for (long K = 0; K <= UB; K++) {
for (long I = 0; I <= UB; I++) {
for (long J = 0; J <= UB; J++) {
long CurrKouho = KyoriArr[I, K] + KyoriArr[K, J];
if (KyoriArr[I, J] > CurrKouho) {
KyoriArr[I, J] = CurrKouho;
}
}
}
}
long PairCnt = 0;
for (long I = 0; I <= UB; I++) {
for (long J = I + 1; J <= UB; J++) {
if (KyoriArr[I, J] <= mP) {
PairCnt++;
}
}
}
return PairCnt;
}
////////////////////////////////////////////////////////////////
// IEnumerable<string>をlongの2次元配列に設定する
////////////////////////////////////////////////////////////////
static long[,] CreateBanArr(IEnumerable<string> pStrEnum)
{
var StrList = pStrEnum.ToList();
if (StrList.Count == 0) {
return new long[0, 0];
}
long[] IntArr = { };
Action<string> SplitAct = pStr =>
IntArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
SplitAct(StrList[0]);
long UB_X = IntArr.GetUpperBound(0);
long UB_Y = StrList.Count - 1;
long[,] WillReturn = new long[UB_X + 1, UB_Y + 1];
for (long Y = 0; Y <= UB_Y; Y++) {
SplitAct(StrList[(int)Y]);
for (long X = 0; X <= UB_X; X++) {
WillReturn[X, Y] = IntArr[X];
}
}
return WillReturn;
}
}