#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define maxN 50005
#define INF 0x3f3f3f3f

struct nod
{
    int b , c;
};

vector <nod> lista[maxN];
queue <int> Q;

int cost[maxN] , cost_aux;
int N , M;

int main ()
{
    freopen ("dijkstra.in" , "r" , stdin);
    freopen ("dijkstra.out" , "w" , stdout);

    scanf ("%d %d" , &N , &M);

    int a;
    nod t;

    for (int i = 1 ; i <= M ; ++i)
    {
        scanf ("%d %d %d" , &a , &t.b , &t.c);
        lista[a].push_back (t);
    }

    for (int i = 2 ; i <= N ; ++i)
        cost[i] = INF;

    int nodd;

    Q.push (1);
    cost[1] = 0;

    while (!Q.empty ())
    {
        nodd = Q.front ();
        for (unsigned i = 0 ; i < lista[nodd].size () ; ++i)
        {
            cost_aux = cost[nodd] + lista[nodd][i].c;
            if (cost[lista[nodd][i].b] > cost_aux)
            {
                cost[lista[nodd][i].b] = cost_aux;
                Q.push (lista[nodd][i].b);
            }
        }
        Q.pop ();
    }

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