#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;

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

const int dmax = 50000;
const int dim = 250000;
const int INF = 250000005;

struct MUCHIE {int a, b, cost;};
MUCHIE m[dim + 1];

int inc[dmax + 1];

int d[dmax + 1];
bool S[dmax + 1];

int N, M;

bool exc(MUCHIE e1, MUCHIE e2)
{
    if(e1.a == e2.a) return e1.b < e2.b;
    else
        return e1.a < e2.a;
}

void Initializare()
{
    int i, x, y, cost;

    in >> N >> M;

    for(i = 1; i <= M; i++)
    {
        in >> x >> y >> cost;

        m[i].a = x;
        m[i].b = y;
        m[i].cost = cost;
    }

    sort(m + 1, m + M + 1, exc);

    inc[ m[1].a ] = 1;

    for(i = 2; i <= M; i++)
        if(m[i].a != m[i-1].a) inc[ m[i].a ] = i;

    for(i = 1; i <= N; i++) d[i] = INF;

    x = 1; // NODUL DE START

    S[x] = true; d[x] = 0;

    //PARCURG VECINII NODULUI x

    for(int i = inc[x]; m[i].a == x; i++)
            d[ m[i].b ] = m[i].cost;
}

void Dijkstra()
{
    int i, j, d_min, nod;

    for(j = 1; j < N; j++)
    {
        d_min = INF;

        for(i = 1; i <= N; i++)
            if(!S[i] && d_min > d[i])
            {
                d_min = d[i];
                nod = i;
            }

        S[nod] = true;

        //PARCURG VECINII NODULUI nod

        for(i = inc[nod]; m[i].a == nod; i++)
            if(d[  m[i].b ] > d[nod] + m[i].cost)
                d[ m[i].b ] = d[nod] + m[i].cost;
    }
}

void Afisare()
{
    for(int i = 2; i <= N; i++)
        if(d[i] == INF) out << 0 <<" ";
        else
            out << d[i] <<" ";
}

int main()
{
    Initializare();
    Dijkstra();
    Afisare();

    return 0;
}