#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

vector <pair <int, int>> g[50005];
int d[50005], use[50005];

int main()
{
    int n, m;
    fin >> n >> m;
    while (m--)
    {
        int a, b, c;
        fin >> a >> b >> c;
        g[a].push_back(make_pair(b, c));
    }
    for (int i = 2; i <= n; i++)
        d[i] = 1000000000;
    for (int i = 1; i <= n; i++)
    {
        int mic = 1000000000, nod;
        for (int j = 1; j <= n; j++)
            if (d[j] < mic && !use[j])
            {
                nod = j;
                mic = d[j];
            }
        use[nod] = 1;
        for (int j = 0; j < g[nod].size(); j++)
            if (d[g[nod][j].first] > d[nod] + g[nod][j].second)
                d[g[nod][j].first] = d[nod] + g[nod][j].second;
    }
    for (int i = 1; i <= n; i++)
        if (d[i] == 1000000000)
            d[i] = 0;
    for (int i = 2; i <= n; i++)
        fout << d[i] << ' ';
    fout << '\n';
    return 0;
}