#include<iostream>
using namespace std;
int main(){
memset(d,0x3f,sizeof(d));
d[k]=0;
for(int i=0;i<n;i++){
long long mn=2147483647;
int id;
for(int j=1;j<=n;j++){
if(!vis[j]&&d[j]<mn){
mn=d[j],id=j;
}
}
if(mn==2147483647){
break;
}
vis[id]=1;
for(int j=0;j<v[id].size();j++){
int to=v[id][j].to;
int len=v[id][j].len;
if(!vis[to]&&d[to]>d[id]+len){
d[to]=d[id]+len;
}
}
}
return 0;
}
