Shared code

#include<iostream>
using namespace std;
#include<climits>


#define N 101
#define mod 1000000007
long long arr[N][N];
long long I[N][N];
long long INF=4e18;


void mul(long long A[][N],long long B[][N],int dim)
{
	long long res[dim+1][dim+1];
	for(int i=0;i<dim;i++){
		for(int j=0;j<dim;j++)
		{
			res[i][j]=(A[i][0]+B[0][j])%mod;
			for(int k=1;k<dim;k++)
			{
				res[i][j]=min(res[i][j],(A[i][k]+B[k][j])%mod);
				res[i][j]%=mod;
			}
		}
	}
	for(int i=0;i<dim;i++)
	{
		for(int j=0;j<dim;j++)
		{
			A[i][j]=res[i][j];
		}
	}
}









void matrixMul(long long a[][N],int dim,long long x )
{
	for(int i=0;i<dim;i++)
	{
		for(int j=0;j<dim;j++)
		{
			if(i==j){
				I[i][j]=1;
			}
			else{
				I[i][j]=0;
			}
		}
	}
	long long n=x;
	while(n)
	{
		if(n%2)
		{
			mul(I,a,dim);
			n--;
		}
		else{
			mul(a,a,dim);
			n=n/2;
		}
	}
	for(int i=0;i<dim;i++)
	{
		for(int j=0;j<dim;j++)
		{
			a[i][j]=I[i][j];
		}
	}
	
	
	
}















int main()
{
	int n;
	cin>>n;
	int m;
	cin>>m;
	long long k;
	cin>>k;
	long long ar[101][101];
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			ar[i][j]=INF;
		}
	}
	for(int i=0;i<m;i++)
	{
		int start,end;
		int weight;
		cin>>start>>end>>weight;
		ar[start-1][end-1]=weight;
	}
	matrixMul(ar,n,k);
	cout<<ar[0][n-1]<<"\n";
}