#include <cstdio>
#include <iostream>
#include <fstream>
using namespace std;
const int MaxN = 50001;
const int inf = 1 << 30;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct graf
{
    int nod, cost;
    graf *urm;
};

int n, m;
graf *a[MaxN];
int d[MaxN], h[MaxN], poz[MaxN], k;

void add(int Unde, int Ce, int Cost)
{
    graf *q = new graf;
    q->nod = Ce;
    q->cost = Cost;
    q->urm = a[Unde];
    a[Unde] = q;
}

void Citire()
{
    f>>n>>m;

    int x, y, z;
    for ( int i = 1; i <= m; i++ )
    {
        f>>x>>y>>z;
        add(x, y, z);
    }
}

void Swap(int x, int y)
{
    int t = h[x];
    h[x] = h[y];
    h[y] = t;
}

void upheap(int X)
{
    int tata;
    while ( X > 1 )
    {
        tata = X /2;

        if ( d[h[tata]] > d[h[X]] )
        {
            poz[h[X]] = tata;
            poz[h[tata]] = X;

            Swap(tata, X);

            X = tata;
        }
        else
            X = 1;
    }
}

void downheap(int X)
{
    int f;
    while ( X <= k )
    {
        f = X;
        if ( (X<<1) <= k )
        {
            f = X << 1;
            if ( f + 1 <= k )
                if ( d[h[f + 1]] < d[h[f]] )
                    f++;
        }
        else
            return;

        if ( d[h[X]] > d[h[f]] )
        {
            poz[h[X]] = f;
            poz[h[f]] = X;

            Swap(X, f);

            X = f;
        }
        else
            return;
    }
}

void dijkstra()
{
    for ( int i = 2; i <= n; ++i )
    {
        d[i] = inf;
        poz[i] = -1;
    }
    poz[1] = 1;

    h[++k] = 1;

    while (k)
    {
        int min = h[1];
        Swap(1, k);
        poz[h[1]] = 1;
        k--;

        downheap(1);

        graf *q = a[min];

        while (q)
        {
            if (d[q->nod] > d[min] + q->cost)
            {
                d[q->nod] = d[min] + q->cost;

                if (poz[q->nod] != -1)
                    upheap( poz[q->nod] );
                else
                {
                    h[++k] = q->nod;
                    poz[h[k]] = k;
                    upheap(k);
                }
            }
            q = q->urm;
        }
    }
}

int main()
{
    Citire();
    dijkstra();

    for ( int i = 2; i <= n; ++i )
        if (d[i]==inf)
            g<<0<<" ";
        else
            g<<d[i]<<" ";
    g.close();

    return 0;
}