#include <cstdio>
#include <vector>
#include <algorithm>
#define INF 1<<30
#define NMAX 50005

using namespace std;
struct graf
{
    int l,r;
};
vector<graf>v[NMAX];
int n,m,x,y,c,lg;
int d[NMAX],H[NMAX*2],Poz[NMAX*2];

graf pp(int x,int y)
{
    graf X;
    X.l=x;X.r=y;
    return X;
}

void urca(int poz)
{
    while(poz > 1 && d[H[poz]] < d[H[poz/2]])
    {
        swap(H[poz],H[poz/2]);
        swap(Poz[H[poz]],Poz[H[poz/2]]);
        poz=poz/2;
    }
}

void bagaheap(int x)
{
    ++lg;
    H[lg] = x;
    Poz[x] = lg;
    urca(lg);
}

void coboara(int poz)
{
    while((poz * 2 <= lg && d[H[poz]] > d[H[poz*2]]) || (poz * 2 + 1 <= lg + 1 && d[H[poz]] > d[H[poz*2+1]]))
    {
        if(poz * 2 + 1 > lg || d[H[poz*2]] < d[H[poz*2+1]])
        {
            swap(H[poz],H[poz*2]);
            swap(Poz[H[poz]],Poz[H[poz*2]]);
            poz=poz*2;
        }
        else
        {
            swap(H[poz],H[poz*2+1]);
            swap(Poz[H[poz]],Poz[H[poz*2+1]]);
            poz=poz*2+1;
        }
    }
}

int Minim()
{
    int Min = H[1];
    swap(H[1],H[lg]);
    swap(Poz[H[1]],Poz[H[lg]]);
    --lg;
    coboara(1);
    return Min;
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        v[x].push_back(pp(y,c));
    }

    for(int i = 2; i <= n; ++i) d[i] = INF;

    bagaheap(1);

    for(int i = 1; i <= n; ++i)
    {
        int x = Minim();

        for(int it = 0; it < v[x].size(); ++it)
        {
            graf X = v[x][it];
            if (d[x] + X.r < d[X.l])
            {
                d[X.l] = d[x] + X.r;
                if (Poz[X.l] == 0) bagaheap(X.l);
                    else urca(Poz[X.l]);
            }
        }
    }

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