#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#define pb push_back
#define INFI 2147483647
#define maxn 50002
#define heap h
#define H h
inline int father(int k){
    return k/2;}
inline int lson(int k){
    return k*2;}
inline int rson(int k){
    return k*2+1;}
using namespace std;
struct varf{
    int i, c;
};


vector<varf> G[maxn];
int n, nh, m, d[maxn], h[maxn], poz[maxn];


void cerne(int k)
{
    int son;
    do
    {
        son=0;
        if(lson(k)<=nh)
        {
            son=lson(k);
            if(rson(k)<=nh && d[h[rson(k)]]<d[h[son]])
                son=rson(k);
            if(d[h[son]]>=d[h[k]])
                son=0;
        }
        if(son)
        {
            swap(h[son], h[k]);
            swap(poz[h[son]], poz[h[k]]);
            k=son;
        }
    }while(son);
}

void promov(int k)
{
    while(k>1 && d[h[father(k)]]>d[h[k]])
    {
        swap(h[father(k)], h[k]);
        swap(poz[h[father(k)]], poz[h[k]]);
        k=father(k);
    }
}

void init(int k)
{
    int i;
    for(i=0;i<=n;i++)
        d[i]=INFI, h[i]=i, poz[i]=i;
    nh=n;
    d[k]=0;
    promov(poz[k]);
}

void dijkstra(int sursa)
{
    init(sursa);
    for(int q=1;q<=n;q++)
    {
        int k=h[1];
        if(d[k]==INFI)
            break;
        h[1]=h[nh--];
        poz[h[1]]=1;
        cerne(1);
        for(int i=0;i<G[k].size();i++)
        {
            varf vec=G[k][i];
            if(d[vec.i]>d[k]+vec.c)
            {
                d[vec.i]=d[k]+vec.c;
                promov(poz[vec.i]);
            }
        }
    }
}

void afis()
{
    int i;
    for(i=2;i<=n;i++)
    {
        if(d[i]==INFI)
            printf("0 ");
        else
            printf("%d ", d[i]);
    }
}

int main()
{
    int i, m;
    ifstream fin("dijkstra.in");
    freopen("dijkstra.out","w",stdout);
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        int x ,y ,c;
        fin>>x>>y>>c;
        varf tmp;
        tmp.i=y;
        tmp.c=c;
        G[x].pb(tmp);
    }
    dijkstra(1);
    afis();
    return 0;
}