#include <algorithm>
#include <fstream>
#include <set>
#include <vector>
#include <cstring>
 
#define INF 0x3f3f3f3f


 
using namespace std;
 

 
vector <pair <int, int> > v[50006];
int d[50006];
pair <int, int> x;
 
int main(){
    ifstream in("dijkstra.in");
	ofstream out("dijkstra.out");
	ios::sync_with_stdio(0);
    in.tie(0);
    int n, m, a, b, c; 
    in >> n >> m;
    
     for(int i = 1; i <= m; i++){
        in >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
    }
    memset(d, INF, sizeof d);
    d[1] = 0;
	set <pair <int, int> > myset;
     
    myset.insert(make_pair(1, 0));
     
    while(!myset.empty()){
         
        int nodcur = myset.begin()->first;
        int distcur = myset.begin()->second; 
        myset.erase(myset.begin());
     
        for(vector <pair <int, int> > :: iterator it = v[nodcur].begin(); it != v[nodcur].end(); ++it){
             
            int nodul = it->first;
            int costul = it->second;
             
            if(d[nodcur] + costul < d[nodul]){
                 
                if(d[nodul] != INF){
                //  x.st = nodul;
                //  x.nd = d[nodul];
                //  myset.erase(myset.find(x));
                    myset.erase(make_pair(nodul, d[nodul]));
                }
                 
                d[nodul] = d[nodcur] + costul;
            //  x.st = nodul;
            //  x.nd = d[nodul];
            //  myset.insert(x);            
                myset.insert(make_pair(nodul, d[nodul]));
            }           
             
        }
         
    }
     
   for (int i = 2; i <= n; ++i) {
        if (d[i] == INF) {
            d[i] = 0;
        }
        out << d[i] << ' ';
    }
     
    return 0;
}