#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
vector <vector<pair<int, int>>> mat; ///struct: int node + int cost
priority_queue<pair<int, int>> q; ///ce pula mea este priority queue?
///priority queue este un queue ce tine elementele sortate pe baza unui comparator
///problema cu priority queue e ca ia descrescator
/*
bool operator < (const struct_nametype &x) const
{
    return cost > x.cost;
}
*/
int m, n, a, b, i, c, dist[50010];
bool viz[50010];
int main()
{
    in >> n >> m;
    mat.resize(n+2);
    for (i = 1; i <= m; i++)
    {
        in >> a >> b >> c;
        mat[a].push_back(make_pair(c, b));
    }
    for (i = 2; i <= n; i++)
        dist[i] = 2e9; ///initializam toate dist cu 2e9 ca sa putem seta minime
    q.push(make_pair(0, 1));
    while(q.size())
    {
        pair<int, int> k = q.top();
        q.pop();
        if (viz[k.second])
            continue;
        viz[k.second] = 1;  ///il setam ca fiind vizitat, e practic asigurat ca acesta este cost minim
        ///deoarece cu priority queue luam mereu costurile cele mai mici de la momentul resp
        for (auto ind : mat[k.second])
        {
            if (dist[ind.second] <= dist[k.second] + ind.first)
                continue; ///este distanta mai mica?
            dist[ind.second] = dist[k.second] + ind.first;
            q.push(make_pair(-dist[ind.second], ind.second));
        }
    }
    for (i = 2; i <= n; i++)
    {
        if (dist[i] == 2e9)
            dist[i] = 0;
        out << dist[i] << ' ';
    }
    return 0;
}