#include <bits/stdc++.h>

using namespace std;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

const int NMAX = 5e4;

int n, m, w;

pair<int, list<int>::iterator> dist[NMAX+1]; //first -> distanta de la i pana la sursa, second -> iteratorul pana la nodul i
vector<pair<int, int>> adj[NMAX+1];

void dial(int src){
    
    list<int> b[w * n + 1];
    
    b[0].push_back(src);
    dist[src].first = 0;
    
    int idx = 0;
    
    while(true){
        
        while(b[idx].size() == 0 and idx < w * n)
            idx ++;
            
        if(idx == w * n)
            break;
            
        int nod = b[idx].front();
        b[idx].pop_front();
        
        for(auto per : adj[nod]){
        
            int next = per.first;
            int cost = per.second;
            
            int dnod = dist[nod].first;
            int dnext = dist[next].first;
            
            if(dnext > dnod + cost){
                
                if(dnext != 1e9)// => este intr-un bucket si-l stergem folosind iteratorul
                    b[dnext].erase(dist[next].second);
                    
                //dam update la noua distanta
                dist[next].first = dnod + cost;
                dnext = dist[next].first;
                
                //bagam iar nodul la distanta corecta in bucket;
                
                b[dnext].push_front(next);
                
                //dam store la noul iteratoru
                
                dist[next].second = b[dnext].begin();
                
            }
        
        }
        
    }
    
    for(int i=1; i<=n; i++)
        if(dist[i].first == 1e9)
            g << 0 << ' ';
        else
            g << dist[i].first << ' ';
    
}

int main()
{
    
    f >> n >> m;
    
    for(int i=1; i<=n; i++)
        dist[i].first = 1e9;
    
    for(int i=1; i<=m; i++){
        
        int x, y, cost;
        f >> x >> y >> cost;
        
        adj[x].push_back({y, cost});
        
        w = max(w, cost);
        
    }
    
    dial(1);
    

    return 0;
}