#include <cstdio>
#include <vector>
using namespace std;

#define nmax 50001
#define inf 0x3f3f3f3f


vector <pair <int,int> > v[nmax];
vector <pair <int,int> >::iterator vecin;
int m,n,nod,i,x,y,c,h[nmax],d[nmax],p[nmax];

inline void swap(int i,int j)
{
    int x;
    x=h[i];
    h[i]=h[j];
    h[j]=x;
    x=p[h[i]];
    p[h[i]]=p[h[j]];
    p[h[j]]=x;
}

void heapup(int i)
{
    if (d[i/2]<d[i]) return;
    swap(i,i/2);
    heapup(i/2);
}

void heapdown(int i)
{
    int st,dr;
    if (i*2>m) return;
    st=d[h[i*2]];
    if (i*2+1<=m) dr=d[h[2*i+1]];
    else dr=st+1;
    if (st<dr)
    {
        if (d[h[i]]<=st) return;
        swap(i,i*2);
        heapdown(i*2);
    }
    else
    {
        if (d[h[i]]<=dr) return;
        swap(i,2*i+1);
        heapdown(i*2+1);
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        v[x].push_back(make_pair(y,c));
        //v[y].push_back(make_pair(x,c));
    }
    for (i=1;i<=n;i++)
    {
        h[i]=i;
        d[i]=inf;
        p[i]=i;
    }
    d[1]=0; d[0]=-1;
    m=n;
    for (i=0;i<n;i++)
    {
        nod=h[1];
        swap(1,m);
        m--;
        heapdown(1);
        for (vecin=v[nod].begin();vecin!=v[nod].end();vecin++)
            if (d[(*vecin).first]>d[nod]+(*vecin).second)
            {
                d[(*vecin).first]=d[nod]+(*vecin).second;
                heapup(p[(*vecin).first]);
            }
    }
    for (i=2;i<=n;i++)
    {
        if (d[i]==inf) printf("0 ");
        else printf("%d ",d[i]);
    }
    return 0;
}