#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define Max 50001
#define Inf 0xfffff

int n,m,d[Max],pos[Max],k;
vector<pair<int,int> >g[Max];
struct nod{ int x,c; }h[Max];

void insert(int x,int c){
    int t,f;
    if( pos[x] == 0 )
    {
        k++;
        h[k].x = x;
        h[k].c = c;
        pos[x] = k;
        f = k;
    }
   else f = pos[x];
        t = f/2;
        while(t > 0 && h[t].c > h[f].c)
        {
            swap(pos[h[t].x],pos[h[f].x]);
            swap(h[t],h[f]);
            f = t; t = f/2;
        }
}

void remove(){
    int t,f;
    pos[h[1].x] = 0;
    h[1] = h[k--];
    pos[h[1].x] = 1;
    t = 1; f = 2;
    if( f+1 <= k && h[f+1].c < h[f].c )f++;
    while( f <= k && h[f].c < h[t].c )
    {
        swap(pos[h[t].x],pos[h[f].x]);
        swap(h[t],h[f]);
        t = f; f = 2* t;
        if( f+1 <= k && h[f+1].c < h[f].c )f++;
    }
}

void dijkstra(){
    int x,y;
    for(int i=2;i<=n;i++)d[i] = Inf;

    insert(1,0);

    while(k > 0)
    {
        x = h[1].x;
        remove();
        for(int i=0;i<g[x].size();i++)
        {
            y = g[x][i].first;
            if( d[y] > d[x] + g[x][i].second )
            {
                d[y] = d[x] + g[x][i].second;
                insert(y,d[y]);
            }
        }
    }
}

int main(){
    int a,b,c;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

        scanf("%d %d",&n,&m);

        for(int i=1;i<=m;i++)
        {
            scanf("%d %d %d",&a,&b,&c);
            g[a].push_back( make_pair(b,c) );
        }

    dijkstra();

        for(int i=2;i<=n;i++)
        if( d[i] == Inf )printf("0 "); else printf("%d ",d[i]);
        printf("\n");

    return 0;
}