#include<iostream>
#include<fstream>
#include<queue>
#include<vector>
#include<climits>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct nod1
{
    unsigned long long nod,dist;
} x;

struct muchie
{
    unsigned long long nod;
    unsigned long long dist;
} muchNoua;

vector <nod1> A ;
vector <bool> K;

vector< vector <muchie> > leg;


 struct compare
 {
   bool operator()(const nod1& l, const nod1& r)
   {
       return l.dist > r.dist;
   }
 };


 priority_queue<nod1,vector<nod1>, compare > heap;

 unsigned long long n, m, contor = 0;

 void citire()
 {
     unsigned long long dist1, nod1, nod2;
     fin>>n>>m;
     leg.resize(n + 1);
     A.resize(n + 1);
     K.resize(n + 1);
     A[1].nod = 1;
     A[1].dist = 0;
     for(int i = 2; i <= n; ++i)
     {
         K[i] = 0;
         A[i].nod = i;
         A[i].dist = ULLONG_MAX;
     }
     for(int i = 1; i <= m; ++i)
     {
         fin>>nod1>>nod2>>dist1;
         muchNoua.nod = nod2;
         muchNoua.dist = dist1;
         leg[nod1].push_back(muchNoua);
     }
 }

int main()
{
    unsigned long long i,y,dist1;
    citire();
    heap.push(A[1]);
    for(int i = 1; i <= n; ++i)
    {
      //  cout<<A[i].dist<<" ";
    }
    //cout<<endl;
    while(!heap.empty())
    {
        x = heap.top();
        i = x.nod;
        heap.pop();
        for(int j = 0; j < leg[i].size(); ++j)
        {
            y = leg[i][j].nod;
            dist1 = leg[i][j].dist;
            //cout<<A[i].dist + dist1<<" "<<j<<" "<<A[y].dist<<endl;
            if(A[i].dist + dist1 < A[y].dist)
            {
                A[y].dist = A[i].dist + dist1;
                heap.push(A[y]);
            }
        }
    }
    for(int i = 2; i <= n; ++i)
    {
        if(A[i].dist == ULLONG_MAX)
        {
            cout<<"0 ";
        }
        fout<<A[i].dist<<" ";
    }
}