#include <fstream>
#include<vector>
#include<queue>
#define INF 49999001
using namespace std;

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

struct nodul{
    int vf, c;
};

vector<nodul> a[50001];
int n,m,x,poz[50001],h[50001],nh,d[50001];

void schimba (int x, int y){
    int u=h[x];
    h[x]=h[y];
    h[y]=u;
    poz[h[x]]=x;
    poz[h[y]]=y;
}

void sterg(int i){
    schimba(i,nh);
    nh--;
}

void urc(int i ){
    while(i>=2 && d[h[i]]<d[h[i/2]]){
        schimba(i,i/2);
        i/=2;
    }
}

void adaug(int x)
{
    h[++nh] = x;
    poz[x] = nh;
    urc(nh);
}

void dijkstra(int xnod){
    int y,cost;
    for (int i = 1; i <= n; i++)
        if(d[i]==0)
            d[i] = INF;
    adaug(xnod);
    //d[xnod] = 0;
    while(nh != 0){
        xnod=h[1];
        sterg(1);
        for(unsigned i=0;i<a[xnod].size(); i++){
            y = a[xnod][i].vf;
            cost = a[xnod][i].c;
            if(d[xnod] + cost < d[y]){
                d[y] = d[xnod] + cost;
                if (poz[y] == 0)
                    adaug(y);
                else
                    urc(poz[y]);
            }
        }
    }
    int minim=INF,nodm=-1;
    for(unsigned i=2;i<=n;i++){
        if(poz[i]==0)
            if(d[i]<minim){
                minim=d[i];
                nodm=i;
            }
    }
    if(nodm!=-1)
        dijkstra(nodm);
}


int main()
{
    int i,na,nb,c,minim=INF,nodm;
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>na>>nb>>c;
        a[na].push_back((nodul){nb,c});
        if(na==1){
            d[nb]=c;
            if(c<minim){
                minim=c;
                nodm=nb;
            }
        }
    }
    dijkstra(nodm);

    for(i=2;i<=n;i++)
        g<<d[i]<<" ";
    return 0;
}