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

struct heap{int x,c;}h[Max];
vector<pair<int,int> >v[Max];
int n,d[Max],pos[Max],k;
bool was[Max];

void remove()
{
    int t,f;
    h[1]=h[k--];
    pos[h[1].x]=1;
    t=1; f=2;
    if(f+1<=k && h[f].c<h[f+1].c)f++;
    while(f<=k && h[f].c<h[t].c)
    {
        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].c<h[f+1].c)f++;
    }
}

void update(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];
        h[f].c=c;
    }
        t=f/2;
        while(t>0 && h[f].c<h[t].c)
        {
            swap(h[t],h[f]);
            swap(pos[h[t].x],pos[h[f].x]);
            f=t; t=f/2;
        }
}

void dijkstra()
{
    int x,y;
    for(int i=2;i<=n;i++)d[i]=Inf;
    k=1;
    h[1].x=1;
    h[1].c=0;
    while(k>0)
    {
        x=h[1].x;
        remove();
        was[x]=1;
        for(int i=0;i<v[x].size();i++)
        {
            y=v[x][i].first;
            if(was[y]==0 && d[y]>d[x]+v[x][i].second)
            {
                d[y]=d[x]+v[x][i].second;
                update(y,d[y]);
            }
        }
    }

}

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

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

        for(int i=2;i<=n;i++) printf("%d ",d[i]==Inf?0:d[i]);
    return 0;
}