#include <bits/stdc++.h>

using namespace std;

#define int long long

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

int n, m, x, y, z, dist[100005];
bool vizit[100005];
priority_queue<pair<int, int>> a;
vector<pair<int, int>> graf[100005];

void setdist() {
    for(int i=1; i<=100003; i++) {
        dist[i]=1e9;
    }
}

void bfs(int nod) {
    a.push({0, nod});
    dist[nod]=0;
    vizit[nod]=true;
    while(a.empty()==false) {
        nod=a.top().second;
        vizit[nod]=true;
        int l=a.top().first;
        a.pop();
        for(auto u : graf[nod]) {
            if(dist[u.first]>-l+u.second) {
                a.push({l-u.second, u.first});
                dist[u.first]=-l+u.second;
            }
        }
    }
}

signed main()
{
    setdist();
    fin >> n >> m;
    for(int i=1; i<=m; i++) {
        fin >> x >> y >> z;
        graf[x].push_back({y, z});
    }
    bfs(1);
    for(int i=2; i<=n; i++) {
        //if(dist[i]==0 && i!=s) {
        //    fout << "-1 ";
        //} else {
            fout << dist[i] << " ";
        //}
    }
    return 0;
}