#include <fstream>
#include <vector>
#include <set>
#define DIM 50002
#define INF 1e9

using namespace std;

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

int n, m, x, y, cost;
int dist[DIM];

struct edge{
    int node;
    int cost;
};

vector<edge> graf[DIM];

class compare{
public:
    bool operator() (edge a, edge b){
        if(a.cost == b.cost)
            return a.node < b.node;
        return a.cost < b.cost;
    }
};

set<edge, compare> s;

int main(int argc, const char * argv[]) {
    in>>n>>m;
    
    for(int i = 1; i <= m; ++ i){
        in>>x>>y>>cost;
        graf[x].push_back({y, cost});
    }
    
    for(int i = 2; i <= n; ++ i)
        dist[i] = INF;
    
    s.insert({1, 0});
    
    while(!s.empty()){
        int nodCurrent = s.begin()->node;
        int costCurrent = s.begin()->cost;
        s.erase(s.begin());
        for(auto it : graf[nodCurrent]){
            int nodNext = it.node;
            int costEdg = it.cost;
            
            if(dist[nodNext] > costCurrent + it.cost){
                auto gasit = s.find({nodNext, dist[nodNext]});
                if(gasit != s.end()){
                    s.erase(gasit);
                }
                dist[nodNext] = costCurrent + it.cost;
                s.insert({nodNext, dist[nodNext]});
            }
            
        }
        
    }
    
    for(int i = 2; i <= n; ++ i){
        if(dist[i] == INF){
            out<<"0 ";
        }
        else{
            out<<dist[i]<<" ";
        }
    }
    
    
    return 0;
}