#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define Max 50001
#define Inf 0xffffff
struct heap{ int x,d; } h[Max];
vector<pair<int,int> >g[Max];
int n,d[Max],pos[Max],k;

void add(int x,int d)
{
    int t,f;
    if( pos[x] == 0 )
    {
        k++;
        h[k].x = x;
        h[k].d = d;
        pos[x] = k;
        f = k;
    } else
    {
        f = pos[x];
        h[f].d = d;
    }
    t = f/2;
    while(t > 0 && h[f].d < h[t].d)
    {
        swap(h[t],h[f]);
        swap(pos[h[t].x],pos[h[f].x]);
        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].d < h[f].d)f++;
    while(f <= k && h[f].d < h[t].d)
    {
        swap(h[t],h[f]);
        swap(pos[h[t].x],pos[h[f].x]);
        t = f; f = 2*t;
        if(f+1<=k && h[f+1].d < h[f].d)f++;
    }
}

void dijkstra()
{
    int x,y;
    for(int i=2;i<=n;i++)d[i] = Inf;
    add(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;
                add(y,d[y]);
            }
        }
    }
}

int main()
{
    int m,x,y,z;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&n,&m);

    while(m--)
    {
        scanf("%d %d %d",&x,&y,&z);
        g[x].push_back(make_pair(y,z));
    }

    dijkstra();

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

    return 0;
}