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