#include<fstream.h>

#define nmax 50100
#define mmax 251000
#define inf 100000000

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int a[mmax], st[mmax], viz[nmax], dis[nmax], n, m, i, j, cost[mmax], prim, x, y, sum, c, min;   

int main()
{
    f>>n>>m;
    for(i=1; i<=m; i++){
        f>>x>>y>>c;
        st[x]++; 
    }
    f.close();    

    sum=0;
    for(i=1; i<=n+2; i++){
        st[i-1]=sum;
        sum=sum+st[i];
    }

    ifstream f("dijkstra.in");
    f>>n>>m;
    for(i=1; i<=m; i++){
        f>>x>>y>>c;
        a[st[x]]=y;
        cost[st[x]]=c;
        st[x]--; 
    }
    f.close();

    for(i=2; i<=n; i++) dis[i]=inf;    
    
    for(i=1; i<=n; i++){
        min=inf;
        for(j=1; j<=n; j++) if( dis[j]<min && !viz[j] ){ min=dis[j]; prim=j; }
        viz[prim]=1;
        for(j=st[prim]+1; j<=st[prim+1]; j++) if( dis[prim]+cost[j] < dis[a[j]] ) dis[a[j]]=dis[prim]+cost[j];
    }

    for(i=2; i<=n; i++) if( dis[i]==inf ) g<<"0 ";
                            else g<<dis[i]<<' ';

    g.close();
    return 0;
}