#include <bits/stdc++.h>
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
const int Nmax = 50005;
const int oo = (1 << 30);
struct Graf
{
    int nod , cost;
    bool operator < (const Graf & e) const
    {
        return cost > e . cost;
    }
};
priority_queue < Graf > Q;
vector < pair < int , int > > L[Nmax];
int dist[Nmax] , n , m;
bool viz[Nmax];
int main()
{
     int x , y , c;
    Graf w , w1;
    fin >> n >> m;
    for(int i = 1 ; i <= m ; i++)
    {
        fin >> x >> y >> c;
        L[x] . push_back({y , c});
    }
    for(int i = 2 ; i <= n ; i++)
        dist[i] = oo;
    w = {1 , 0};
    Q . push(w);
    while(! Q . empty())
    {
        w = Q . top();
        Q . pop();
        if(! viz[w . nod])
        {
            viz[w . nod] = true;
            for(auto k : L[w . nod])
            {
                if(dist[k . first] > dist[w . nod] + k . second)
                {
                    dist[k . first] = dist[w . nod] + k . second;
                    w1 = {k . first , dist[k . first]};
                    Q . push(w1);
                }
            }
        }
    }
    for(int i = 2 ; i <= n ; i++)
        if(dist[i] == oo)
            fout << "0 ";
    else fout << dist[i] << " ";
    fout << "\n";
    fin.close();
    fout.close();
    return 0;
}