#include <bits/stdc++.h>

using namespace std;
const int oo =  1e9;
int n, m;
int d[50009], use[50009];
vector<pair<int, int>> g[50009];

void dijkstra(int source)
{
    for (int i = 2; i <= n; i++) d[i]=oo;
    for (int i = 1; i <= n; i++)
    {
        int min=oo, nod;
        for (int i = 1; i <= n; i++)
            if (d[i] < min && use[i] == 0)
                min = d[i], nod=i;

                use[nod]=1;
                for (int i = 0; i < (int)g[nod].size(); ++i)
                {
                    int vecin = g[nod][i].first;
                    int cost = g[nod][i].second;
                    if (d[nod] + cost < d[vecin])
                        d[vecin] = d[nod] + cost;
                }
            }
    }
}
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
int main()
{
    fin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        g[x].push_back(make_pair(y, c));
    }

    dijkstra(1);
    for (int i = 2; i <= n; i++)
        fout << d[i] << " ";
    return 0;
}