#include <bits/stdc++.h>
#define nmax 50004
#define infinit 10000004
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n , m , viz[nmax] , d[nmax];
        ///   nod   cost
vector < pair<int , int> > L[nmax];
        ///           cost   nod
priority_queue < pair <int , int> > q;
void Citire()
{
    int i , x , y , c;
    fin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        L[x].push_back({y , c});
    }
    fin.close();
}
void Dijkstra()
{
    int i , cost , k;
    for(i = 1; i <= n; i++)
        d[i] = infinit;
    d[1] = 0;
    viz[1] = 1;
    q.push({0 , 1});
    while(!q.empty())
    {
        k = q.top().second;
        q.pop();
        viz[k] = 0;
        for(auto j : L[k])
           {
               i = j.first;
               cost = j.second;
                    if(d[i] > (d[k] + cost))
                {
                    d[i] = d[k] + cost;
                    if(viz[i] == 0)
                    {
                        viz[i] = 1;
                        q.push({-d[i] , i});
                    }
                }

            }
    }
    for(i = 2; i <= n; i++)
        fout << d[i] << " ";
}
int main()
{
    Citire();
    Dijkstra();
    return 0;
}