#include<fstream.h>

#define inf 2000000
#define nmax 50100
#define mmax 250100

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

int n, m, dis[nmax], nr, i, sum, x, y, pret, el, j;
short int st[nmax], a[mmax*2], cos[mmax*2], heap[nmax], viz[nmax];

void ridica(int x)
{
    int val;
    val=heap[x];
    while( x>1 && dis[val] < dis[heap[x>>1]] ){
        heap[x]=heap[x>>1];
        x>>=1;
    }

    heap[x]=val;
    viz[x]=val;
}

void scufunda(int x)
{
    int fiu, sar=x;
    while( (x<<1) < nr ){
        fiu=x<<1;
        if( (fiu|1) < nr && dis[heap[fiu]] > dis[heap[fiu|1]] ) fiu|=1;
        if( dis[heap[x]] > dis[heap[fiu]] ){
            int aux=heap[x];
            heap[x]=heap[fiu];
            heap[fiu]=aux;
            x<<=1;
        }
            else break;
    }
    viz[sar]=x;
}

void parc(int x)
{
    int i;
    for(i=st[x]+1; i<=st[x+1]; i++){ 
        if( viz[a[i]]==-1 ){ heap[++nr]=a[i]; viz[a[i]]=nr; } 
        if( dis[x]+cos[i] < dis[a[i]] ){ 
            dis[a[i]]=dis[x]+cos[i];
            ridica(viz[a[i]]);
        }
    }
}  

int main()
{
    f>>n>>m;
    for(i=1; i<=m; i++){
        f>>x>>y>>pret;
        st[x]++;
        st[y]++;
    }
    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>>pret;
        a[st[x]]=y;    cos[st[x]]=pret;
        a[st[y]]=x;    cos[st[y]]=pret;
        st[x]--;    st[y]--;
    }
    f.close();

    for(i=2; i<=n; i++) viz[i]=-1;
    heap[1]=1; nr=1;
    dis[1]=0;
    for(i=2; i<=n; i++) dis[i]=inf;
    for(i=1; i<=n; i++){
        el=heap[1];
        heap[1]=heap[nr--];
        scufunda(1);
        parc(el);
    } 
    
    for(i=2; i<=n; i++) if(dis[i]==inf) g<<"0 ";
                            else g<<dis[i]<<' ';

    g.close();
    return 0;
}