#include <bits/stdc++.h>
#define INF 20001
using namespace std;
int n, i, x, m, a, b, c;
short int d[50005];
struct muchie
{
    int cost;
    int val;
}aux, minn;
struct cmp
{
    bool operator()(muchie i, muchie j)
    {
        return i.cost > j.cost;
    }
};
priority_queue<muchie, vector<muchie>, cmp >Q;
vector <muchie>v[50005];
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;
        aux.val = b;
        aux.cost = c;
        if(a == 1)d[b] = c, Q.push(aux);
        else v[a].push_back(aux);
    }
    while(true)
    {
        if(Q.empty())break;
        minn = Q.top();
        Q.pop();
        for(i = 0; i < v[minn.val].size(); i ++)
        {
            aux = v[minn.val][i];
            if(d[aux.val] > minn.cost + aux.cost)
            {
                d[aux.val] = minn.cost + aux.cost;
                muchie aux1;
                aux1.val = aux.val;
                aux1.cost = d[aux.val];
                Q.push(aux1);
            }
        }
    }
    for(i = 2; i <= n; i ++)
        if(d[i] == INF)g << 0 << " ";
        else g << d[i] << " ";
    return 0;
}