#include <bits/stdc++.h>
#define INF 1000000
#define Dmax 20005
using namespace std;
struct muchie
{
    int cost;
    int val;
}aux;
deque <int> bucket[Dmax];
vector < muchie> v[50005];
int n, m, i, d[50005], a, b, c, k, poz, maxx;
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f >> n >> m;
    for(i = 1; i <= n; i ++)
        d[i] = INF;
    for(i = 1; i <= m; i ++)
    {
        f >> a >> b >> c;
        if(c > maxx)maxx = c;
        aux.val = b;
        aux.cost = c;
        if(a == 1)bucket[c].push_back(b), d[b] = c;
        else v[a].push_back(aux);
    }
    while(true)
    {
        while(bucket[k].size() == 0 && k <= maxx)k++;
        if(k > maxx)break;
        poz = bucket[k].front();
        bucket[k].pop_front();
        if(d[poz] != k)continue;
        for(i = 0; i < v[poz].size(); i ++)
        {
            aux = v[poz][i];
            if(d[aux.val] > d[poz] + aux.cost)
            {
                d[aux.val] = d[poz] + aux.cost;
                bucket[d[aux.val]].push_back(aux.val);
                maxx = max(maxx, d[aux.val]);
            }
        }
    }
    for(i = 2; i <= n; i ++)
        if(d[i] == INF)g << "0" << " ";
        else g << d[i] << " ";
    return 0;
}