#include <iostream>
#include <fstream>

using namespace std;

struct edge
{
    int s, d, c;
};

struct graph
{
    int n, m;
    edge x[12501];
};

bool used[50001];

int koltseg(const graph &g)
{
    int sum = 0;
    for (int i = 0; i < g.m; ++i)
        sum += g.x[i].c;
    return sum + 1;
}

void beolvas(graph &g)
{
    ifstream fcin("dijkstra.in");
    fcin >> g.n >> g.m;
    for (int i = 0; i < g.m; ++i)
        fcin >> g.x[i].s >> g.x[i].d >> g.x[i].c;
}

void kiir(int D[], int n)
{
    ofstream fcout("dijkstra.out");
    for (int i = 2; i <= n; ++i)
        fcout << D[i] << ' ';
}

int keres(int D[], int n)
{
    int mini, idx = 1;
    for (; used[idx]; ++idx);
    mini = idx;
    for (; idx <= n; ++idx)
        if (!used[idx] && D[idx] < D[mini])
            mini = idx;
    return mini;
}


void dijkstra(const graph &g, int D[])
{
    for (int menet = 1; menet < g.n; ++menet)
    {
        int mini = keres(D, g.n);
        used[mini] = true;
        for (int i = 0; i < g.m; ++i)
        {
            if (g.x[i].s == mini && !used[g.x[i].d])
                if (D[mini] + g.x[i].c < D[g.x[i].d])
                    D[g.x[i].d] = D[mini] + g.x[i].c;
        }
    }
}

int main()
{
    graph g;
    beolvas(g);

    int maxCost = koltseg(g);
    int D[50001];
    for (int i = 2; i <= g.n; ++i)
        D[i] = maxCost;
    D[1] = 0;

    dijkstra(g, D);
    for (int i = 1; i <= g.n; ++i)
        if (D[i] == maxCost)
            D[i] = 0;
    kiir(D, g.n);
}