#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <utility>

using namespace std;

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

const int INF_MAX = 2e9+20;

struct op{
    bool operator()(const pair<int, int>& x, const pair<int, int>& y){
     return x.second > y.second;
    }
}myFn;

bool visited[50001];
int d[50001];
vector<pair<int, int>> w[250001];
priority_queue<pair<int, int>, vector<pair<int, int>>, op> pq;

void dijkstra(){
    while(pq.empty() == false){
        int currentNode = pq.top().first;
        int distance = pq.top().second;
        pq.pop();
        if(visited[currentNode] == true) continue;
        d[currentNode] = distance;
        visited[currentNode] = true;
        for(auto it : w[currentNode]){
            if(distance + it.second  < d[it.first]){
                pq.push({it.first, distance + it.second});
            }
        }
    }
}

int main(){
    int N, M;
    in >> N >> M;

    for(int i = 1; i<=50000; i++)
        d[i] = INF_MAX;

    for(int i = 0; i<M; i++){
        int a, b, c;
        in >> a >> b >> c;
        w[a].push_back({b, c});
    }   
    for(auto it : w[1]){
        pq.push(it);
    }
    d[1] = 0;
    dijkstra(); 
    for(int i = 2; i<=N; i++) out << d[i] << " ";
}