#include <bits/stdc++.h>
using std::ifstream;
using std::ofstream;
using std::cout;
ifstream fin ( "bellmanford.in" );
ofstream fout( "bellmanford.out" );
constexpr int NMAX = 50002;
constexpr int VMAX = 250002;
constexpr int INFINITE = 9999999;

int distance[NMAX], predecessor[NMAX];
struct muchie { int a, b, cost; } e [VMAX];
int n, m;

void bellmanford()
{
    // step 1: Initialize
    for (int i = 1; i <= n; i++)
    {
        distance[i] = INFINITE;
        // predecessor[i] = 0;
    }

    distance[1] = 0;

    // step 2: Relax edges repeatedly
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            muchie& m = e[j];
            if (distance[m.a] != INFINITE &&
                distance[m.b] > distance[m.a] + m.cost)
            {
                distance[m.b] = distance[m.a] + m.cost;
                predecessor[m.b] = m.a;
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        e[i] = { a, b, c };
    }

    bellmanford();

    for (int i = 2; i <= n; i++)
    {
        cout << distance[i] << ' ';
    }

    return 0;
}