#include <iostream>
#include <vector>
#include <algorithm>
#include <list>
#include <queue>
#include <cstring>
#define ll long long
#define ps push_back
using namespace std;
struct node{
    int idx;
    ll shortest_path;

    node(int i,ll s){
        idx = i;
        shortest_path = s;
    }
    bool operator < (const node &tmp) const {
        return shortest_path > tmp.shortest_path;
    }
};
vector<pair<int,int>> graph[100050];
int main() {
    int n,m;
    cin >>n >> m;

    for(int i = 0;i<m;i++){
        ll a,b,c;
        cin >> a >> b>> c;
        graph[a].push_back(make_pair(b, c));
//        graph[b].push_back(make_pair(a, c));
    }


        priority_queue<node> pq;
        vector<ll> dist(n+1,1e18);
        vector<bool> visited(n+1,false);
        dist[1] = 0;
        pq.push(node(1,0));

        while(!pq.empty()){
            node curr = pq.top();
            pq.pop();

            if(visited[curr.idx]) continue;
            visited[curr.idx] = true;
            for(int j = 0;j<graph[curr.idx].size();j++){
                int sosed = graph[curr.idx][j].first;
                ll pat =  graph[curr.idx][j].second;

                if(!visited[sosed] and curr.shortest_path+pat < dist[sosed]){
                    pq.push(node(sosed,curr.shortest_path+pat));
                    dist[sosed] = curr.shortest_path+pat;

                }
            }
        }
    for(int i = 1;i<= n;i++){
        cout << dist[i] << " " ;
    }
}