#include <fstream>
#include <vector>
#define LS (node<<1)
#define RS ((node<<1)+1)
#define  INF (1<<30)
#define IMAX (1<<17)
#define NMAX 50004
 
using namespace std;
 
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
 
int N,M,D[NMAX],Dist[NMAX];
 
vector<pair<int,int> > V[NMAX];
 
int AInt[IMAX];
 
void Refresh(int node,int start,int final)
{
    if(start == final)
        AInt[node] = start;
    else
    {
        int med = (start + final) / 2;
        Refresh(LS,start,med);
        Refresh(RS,med+1,final);
        if(D[AInt[LS]] < D[AInt[RS]])
             AInt[node] = AInt[LS];
        else AInt[node] = AInt[RS];
    }
}
 
void Update(int node,int start,int final,int pos)
{
    if(start == final);
    else
    {
        int med = (start + final) / 2;
        if(pos<=med)
             Update(LS,start,med,pos);
        else Update(RS,med+1,final,pos);
         
        if(D[AInt[LS]] < D[AInt[RS]])
             AInt[node] = AInt[LS];
        else AInt[node] = AInt[RS];
    }
}
int main ()
{
    int i,x,y,c;
    int Empty = 1;
    in>>N>>M;
    while(M--)
    {
        in>>x>>y>>c;
        V[x].push_back(make_pair(y,c));
    //  V[y].push_back(make_pair(x,c));
    }
    for(i=2;i<=N;i++)
        D[i] = Dist[i] = INF;
     
    Refresh(1,1,N);
     
    while(Empty)
    {
        x = AInt[1];//TOP
        //POP
        if(D[x] == INF)
            Empty = 1;
        D[x] = INF;
        Update(1,1,N,x);
        for(i=0;i<V[x].size();i++)
        {
            y = V[x][i].first;
            c = V[x][i].second;
            if(Dist[y] > Dist[x]+c)
                D[y] = Dist[y] = Dist[x]+c,Update(1,1,N,y),Empty ++;
        }
        Empty--;
    }
    for(i=2;i<=N;i++)
        out<<(Dist[i]!= INF ? Dist[i] : 0)<<' ';
}