#include <fstream>
#include <vector>
#include <queue>
#include <iostream>
#include <bitset>
#include <climits>
#define INF INT_MAX

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, dist[50005];

bitset <50005> viz;

vector < pair <int, int> > v[50005];

priority_queue < pair <int, int> > heap;

void Dijkstra()
{
    for(int i = 1; i <= n; ++i) // initializare vector distanta cu infinit
        dist[i] = INF;

    dist[1] = 0;

    heap.push(make_pair(0, 1));
    while(!heap.empty())
    {
        int nod = heap.top().second;
        heap.pop();

        if(viz[nod]) continue;
        viz[nod]=1;
        for(int i=0; i<v[nod].size(); i++)
        {
            int p, q;
            p = v[nod][i].first;
            q = v[nod][i].second;
            /// drum de la nodul nod la nodul p cu costul q
            if(dist[p] > dist[nod] + q)
            {
                dist[p] = dist[nod] + q;
                heap.push(make_pair(dist[p], p)); /// -dist[p] daca e cea mai mica va fi prima in pq, va avea prioritate
            }
        }
    }
}

int main()
{
    int m, x, y, cost;
    f >> n >> m;
    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>cost;
        v[x].push_back(make_pair(y, cost));
    }

    Dijkstra();

    for(int i=2; i<=n; i++)
        if(dist[i] != INF)
            g<<dist[i]<<" ";
        else g<<0<<" ";
    f.close();
    g.close();
    return 0;
}