#include <bits/stdc++.h>
using namespace std;
struct muchie
{
    int dest;
    int cost;
}aux, aux1;
struct cmp
{
    bool operator () (muchie i, muchie j)
    {
        return i.cost > j.cost;
    }
};
vector <muchie> v[50005];
priority_queue<muchie, vector<muchie>, cmp> Q;
int n, m, i, x, y, c, d[50005];
int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(i = 2; i <= n; i ++)
        d[i] = INT_MAX;
    for(i = 1; i <= m; i ++)
    {
        scanf("%d %d %d", &x, &y, &c);
        aux.dest = y;
        aux.cost = c;
        v[x].push_back(aux);
        if(x == 1)
        {
            d[y] = c;
            aux.dest = y;
            Q.push(aux);
        }
    }
    while(!Q.empty())
    {
        aux = Q.top();
        Q.pop();
        if(aux.cost != d[aux.dest])continue;
        for(i = 0; i < v[aux.dest].size(); i ++)
        {
            aux1 = v[aux.dest][i];
            if(d[aux1.dest] > aux.cost + aux1.cost)
            {
                d[aux1.dest] = aux.cost + aux1.cost;
                aux1.cost = d[aux1.dest];
                Q.push(aux1);
            }
        }
    }
    for(i = 2; i <= n; i ++)
        if(d[i] != INT_MAX)printf("%d ", d[i]);
        else printf("%d ", 0);
    return 0;
}