#include <bits/stdc++.h>
#define VAL_MAX 1000000001
using namespace std;
int n, m, i, A, B, C, d[50005];
struct muchie
{
    int x, cost;
}aux, aux1;
struct cmp
{
    bool operator()(muchie i, muchie j)
    {
        return i.cost > j.cost;                        //Min_Heap
    }
};
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] = VAL_MAX;
    for(i = 1; i <= m; i ++)
    {
        f >> A >> B >> C;
        if(A == 1)
        {
            d[B] = C;
            aux.x = B;
            aux.cost = C;
            Q.push(aux);
        }
        else
        {
            aux.x = B;
            aux.cost = C;
            v[A].push_back(aux);
        }
    }
    while(!Q.empty())
    {
        aux = Q.top();
        Q.pop();
        if(aux.cost != d[aux.x])continue;
        for(i = 0; i < v[aux.x].size(); i ++)
        {
            aux1 = v[aux.x][i];
            if(d[aux1.x] > d[aux.x] + aux1.cost)
            {
                d[aux1.x] = d[aux.x] + aux1.cost;
                aux1.cost = d[aux1.x];
                Q.push(aux1);
            }
        }
    }
    for(i = 2; i <= n; i ++)
        if(d[i] != VAL_MAX)g << d[i] << " ";
        else g << 0 << " ";
    return 0;
}