/*  
    * author: qvalentin  
    * https://codeforces.com/profile/qvalentin
    * 
    * It's you, it'll always be you *
 
*/
 
 
#include <bits/stdc++.h>  
using namespace std;  
#define ull unsigned long long  
#define ll long long  
#define fastio ios_base::sync_with_stdio(0); cin.tie(nullptr);  
const int MOD = 1e9+7;
int di[4]={0,0,-1,1};  
int dj[4]={-1,1,0,0};  
      
string FILENAME="djikstra";  
ifstream f(FILENAME+".in");  
ofstream g(FILENAME+".out");  
 
template <typename T>


class Heap{
        vector<T> v;

        public:
        //fctiile cerute
        void insert(T x){
                v.push_back(x);
                int i = v.size() - 1;
                while(i>0 && v[i] < v[(i - 1) / 2]) {
                        swap(v[i], v[(i - 1) / 2]);
                        i = (i - 1) / 2;
                }
        }

        T top() const{
                return v.front();
        }

        void pop(){
                //
                v[0] = v.back();
                v.pop_back();


                int i = 0;
                while(true){
                        
                        int mxi = i;
                        int st = 2*i + 1;
                        int dr = 2*i + 2;

                        if(st < v.size() && v[st] < v[mxi]) mxi = st;
                        
                        if(dr < v.size() && v[dr] < v[mxi]) mxi = dr;

                        if(i!=mxi){
                                swap(v[i], v[mxi]);
                                i = mxi;

                        }
                        else break;
                }
        }

        //helper fct
        int size() const {
                return v.size();
        }

};


void djik(int start, int n, vector<vector<int> >& a){
        vector<int> d(n+1, INT_MAX);

        //{dist pana la nod, nod}
        Heap<pair<int, int> >hp;

        d[start] = 0;
        hp.insert({0,start});

        while(hp.size() > 0) { 
                pair<int, int> curr = hp.top();
                hp.pop();

                int dist = curr.first;
                int u = curr.second;

                if(dist > d[u]) continue;
                

                for(int v = 1; v<=n; ++v) {
                        if(a[u][v] != 0 && a[u][v] != INT_MAX) {
                                if(d[u] + a[u][v] < d[v]){
                                        d[v] = d[u] + a[u][v];
                                        hp.insert({d[v],v});
                                }
                        }
                }
        }

        for(int i=1;i<=n;++i)cout<<d[i]<< ' ';
}

signed main(){  
        #ifndef qv
                #define cin f
                #define cout g
        #endif

        int n,m;
        cin>>n>>m;
        vector<vector<int> > a(n+1,vector<int>(n+1, INT_MAX));

        for(int i=1;i<=m;++i){
                int x,y,c;
                cin>>x>>y>>c;
                a[x][y] = c;
        }
        djik(1,n,a);




        return 0;
    
}