#include<fstream.h>

#define nmax 50100
#define mmax 500010
#define inf 100000
   
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m, a[mmax], st[nmax], dis[nmax], cost[mmax], heap[nmax], poz[nmax], i, el, nr;
 
void citire()
{
    int x, y, pret, i, sum;

    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;
        a[st[y]]=x;
        cost[st[x]]=pret;
        cost[st[y]]=pret;
        st[x]--; st[y]--;
    }
    f.close();
}

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

void scufunda(int p)
{
    int fiu, aux;
    
    while( (p<<1) < nr ){
        fiu=p<<1;
        if( fiu|1 < nr && dis[heap[fiu]] > dis[heap[fiu|1]] ) fiu|=1;
        
        if( dis[heap[fiu]] < dis[heap[p]] ){
            aux=fiu;
            fiu=p;
            p=fiu;

            aux=heap[fiu];
            heap[fiu]=heap[p];
            heap[p]=heap[fiu];

            poz[p]=heap[p];
            poz[fiu]=heap[fiu];
        }
            else break;
    }
}
            
void parc(int p)
{
    for(i=st[p]+1; i<=st[p+1]; i++) 
        if( dis[a[i]] < dis[p] + cost[i] ){
            dis[a[i]] = dis[p] + cost[i];
            ridica(poz[a[i]]);
        }
}

int main()
{
    citire();
    
    for(i=2; i<=n; i++){
        dis[i]=inf;
        poz[i]=i;
        heap[i]=i;
    }

    dis[1]=0; poz[i]=1;
    for(i=1; i<=n; i++){
        el=heap[1]; 
        heap[1]=heap[nr--];
        scufunda(1);

        parc(el);
    }

    for(i=2; i<=n; i++) g<<dis[i]<<' ';
    g.close();
    return 0;
}