#include <bits/stdc++.h>
#define INF 1000000007
using namespace std;
struct muchie
{
    int dest;          //destinatia
    int cost;          //costul de a ajunge acolo
}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 i, n, m, d[50005], prec[50005], x, y, c;
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f >> n >> m;
    for(i = 1; i <= n; i ++)
    {
        d[i] = INF;            //d[i] = lungimea traseului de la nodul 1 (cel de start) la nodul i
        prec[i] = INF;         //prec[i] = nodul precedent in drumul facut de la nodul 1 la nodul i (folositor la gasirea drumului)
    }
    for(i = 1; i <= m; i ++)
    {
        f >> x >> y >> c;
        aux.dest = y;
        aux.cost = c;
        v[x].push_back(aux);
        if(x == 1)
        {
            d[y] = c;
            prec[y] = 1;
            Q.push(aux);
        }
    }
    while(!Q.empty())
    {
        aux = Q.top();
        Q.pop();
        if(aux.cost != d[aux.dest])continue;       //optimizare pentru timp de rulare eficient
        for(i = 0; i < v[aux.dest].size(); i ++) //parcurgem vecinii lui aux.dest
        {
            aux1 = v[aux.dest][i];
            if(d[aux1.dest] > aux.cost + aux1.cost)         // daca lungimea lui 1 -> i este mai mare decat 1 -> aux.dest -> i, actualizam drumul minim gasit
            {
                d[aux1.dest] = aux.cost + aux1.cost;
                aux1.cost = d[aux1.dest];
                Q.push(aux1);
                prec[aux1.dest] = aux.dest;
            }
        }
    }
    for(i = 2; i <= n; i ++)
        g << d[i] << " ";
    return 0;
}