#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>

#define ls(x) (x<<1)
#define rs(x) ((x<<1)+1)
#define fth(x) (x>>1)
#define INF (1<<30)

using namespace std;

struct nod
{
    int y, v;
}nd;

int n, m, i, x, y, z, q, w, hp[50005], b[50005], c[50005], pz[50005];
vector <nod> v[50005];
vector <nod>::iterator it;

void C(int x, int y)
{
    int aux=0;
    pz[hp[x]]=y;pz[hp[y]]=x;
    aux=hp[x];hp[x]=hp[y];hp[y]=aux;
}

int S(int x, int y)
{
    if(b[hp[x]]<=b[hp[y]]) return 1;
    return 0;
}

void UP(int x)
{
    if(x==1) return;
    if(S(fth(x), x)) return;
    C(fth(x), x);
    UP(fth(x));
}

void DOWN(int x)
{
    if(ls(x)>q) return;
    int son=ls(x);
    if(son+1<=q&&S(son+1, son)) son++;
    if(S(x, son)) return;
    C(x, son);
    DOWN(son);
}

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, &z);
        nd.y=y;nd.v=z;
        v[x].push_back(nd);
    }
    for(i=2;i<=n;i++)
    {
        b[i]=INF;
        c[i]=INF;
        hp[++q]=i;
        pz[i]=q;
    }
    w=q;
    x=1;
    while(1)
    {
        for(it=v[x].begin();it!=v[x].end();it++)
        {
            nd=*it;
            if(c[x]+nd.v<c[nd.y])
            {
                if(b[nd.y]==INF+69)
                {
                    c[nd.y]=c[x]+nd.v;
                    continue;
                }
                c[nd.y]=c[x]+nd.v;
                b[nd.y]=c[nd.y];
                UP(pz[nd.y]);
            }
        }
        if(w==0) break;
        x=hp[1];
        b[x]=INF+69;
        w--;
        DOWN(1);
    }
    for(i=2;i<=n;i++)
    {
        if(c[i]>=INF) printf("0 ");
        else printf("%d ", c[i]);
    }
    return 0;
}