1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 using namespace std; 8 int value[10010],to[10010],next[10010]; 9 int head[10010],total;10 int book[10010];11 int dis[10010];12 int n,m;13 void adl(int a,int b,int c)14 {15 total++;16 to[total]=b;17 value[total]=c;18 next[total]=head[a];19 head[a]=total;20 }21 void dijkstra(int u)22 {23 memset(dis,88,sizeof(dis));24 memset(book,0,sizeof(book));25 dis[u]=0;26 for(int i=1;i<=n;i++)27 {28 int start=-1;29 for(int j=1;j<=n;j++)30 if(book[j]==0 && (dis[start]>dis[j] || start==-1))31 start=j;32 book[start]=1;33 for(int e=head[start];e;e=next[e])34 dis[to[e]]=min(dis[to[e]],dis[start]+value[e]);35 }36 }37 int main()38 {39 cin>>n>>m;40 for(int i=1;i<=m;i++)41 {42 int a,b,c;43 cin>>a>>b>>c;44 adl(a,b,c);45 } 46 dijkstra(1);47 for(int i=1;i<=n;i++)48 cout<
            
             <<" ";49 }