#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <algorithm>
#include <set>
using namespace std;
 
typedef long long ll;
#define pb push_back
#define mp make_pair
#define f first
#define s second
 
 
vector<pair<int, int>> graph[100005];
long long dist[100005];
bool visited[100005];
int main()
{
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
//    ifstream cin("in.txt");
 
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        graph[a-1].pb(mp(b-1, c));
    }
    for(int i =0 ; i < n; i++) {
        dist[i] = 1e18;
        visited[i] = false;
//        sort(graph[i].begin(), graph[i].end(), [&](const pair<int, int> &a, const pair<int, int> &b) {
//            return a.second < b.second;
//        });
    }

    
    set<pair<int, long long> > pq;
    dist[0] = 0;
    pq.insert(make_pair(0, 0));
    while(!pq.empty()){
        pair<int, long long> c = *pq.begin();
        pq.erase(pq.begin());
        for(int i = 0; i < (int) graph[c.first].size(); i++){
            int z = graph[c.first][i].f;
            if(c.second + graph[c.first][i].second < dist[z]) {
                pq.erase(make_pair(z, dist[z]));
                dist[z] = c.second + graph[c.first][i].second;
                pq.insert(make_pair(z, dist[z]));
                
            }
        }
    }
    for(int i = 0; i < n; i++){
        cout << dist[i] << " ";
    }
    
    
    return 0;
 
}