#include<fstream> 
using namespace std; 
ifstream in("ubuntzei.in"); 
ofstream out("ubuntzei.out");
const int INF = 0x3F3F3F3F;
int main() 
{int i,j, A[100][100],n,m,k,orasetrec, v[1000], c;

in>>n>>m;
in>>orasetrec; for(i=1;i<=orasetrec;i++) 
        in>>v[i];

		
        for(i=1;i<=n;i++) 
		for(j=1;j<=n;j++) 
		if(i==j) A[i][j]=0; 
		else 
			A[i][j]=INF; 
		
		while(in>>i>>j>>c) 
		 A[i][j]=A[j][i]=c; 
		
		
			
			for(k=1;k<=n;k++) 
	for(i=1;i<=n;i++) 
		for(j=1;j<=n;j++) 
			if(A[i][j]>A[i][k]+A[k][j]) 
				A[i][j]=A[i][k]+A[k][j]; 
			
				
			out<<A[1][n]; 
			

 

}