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

#define nmax 50001
#define inf 0x3f3f3f3f

struct muchie{
    int y,c;
};

vector <muchie> g[nmax];
int cost[nmax],p[nmax],h[nmax];
int n,m,i,x,y,nod,c;

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

inline void heapup(int i)
{
    if (cost[h[i]]>cost[h[i/2]]) return;
    swap(i,i/2);
    heapup(i/2);
}

inline void heapdown(int i)
{
    int st,dr;
    if (i*2>m) return;
    st=cost[h[2*i]];
    if (i*2+1<=m) dr=cost[h[2*i+1]];
    else dr=st+1;
    if (st<dr)
    {
        if (cost[h[i]]<=st) return;
        swap(i,i*2);
        heapdown(i*2);
    }
    else
    {
        if (cost[h[i]]<=dr) return;
        swap(i,i*2+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);
        g[x].push_back((muchie){y,c});
    }
    for (i=1;i<=n;i++)
    {
        cost[i]=inf;
        h[i]=i;
        p[i]=i;
    }
    m=n;
    cost[1]=0;
    cost[0]=-1;
    for (i=0;i<n;i++)
    {
        nod=h[1];
        swap(1,m);
        m--;
        heapdown(1);
        for (int j=0;j<g[nod].size();j++)
            if (cost[ g[nod][j].y ]>cost[nod]+g[nod][j].c)
            {
                cost[ g[nod][j].y ]=cost[nod]+g[nod][j].c;
                heapup(p[g[nod][j].y]);
            }
    }
    for (i=2;i<=n;i++)
        if (cost[i]!=inf)
            printf("%d ",cost[i]);
        else printf("0 ");
    return 0;
}