#include <bits/stdc++.h>
#define NUM 50005
#define inf 0x3f3f3f3f
using namespace std;

// pair<cost, vecin>
vector <pair<int, int>> graf[NUM];
priority_queue< pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > heap;
int d[NUM];

int n, p, a, b, c, pmin, m, distAux;
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f >> n >> m;

    p = 1;
    while(f >> a >> b >> c)
        graf[a].push_back(make_pair(c, b));

    for(int i = 0; i <= n; ++i)
        d[i] = inf;



    d[p] = 0;
    heap.push(make_pair(0, p));


    while(!heap.empty())
    {
        distAux = heap.top().first;
        pmin = heap.top().second;
        heap.pop();

        if(distAux > d[pmin])
            continue;

        for(int i = 0; i < graf[pmin].size(); ++i)
        {
            int nod = graf[pmin][i].second;
            int cost = graf[pmin][i].first;
            if(d[nod] > d[pmin] + cost)
            {
                d[nod] = d[pmin] + cost;
                heap.push(make_pair(d[nod], nod));
            }
        }
    }

    for(int i = 2; i <= n; ++i)
        if(d[i] == inf)
            g << "0 ";
        else
            g << d[i] << " ";

    f.close();
    g.close();
}