#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1000000005
#define LINF 1000000000000000005
#define MAXN 50005
#define mp make_pair
#define pi pair<int,int>
#define pl pair<ll,ll>
#define vi vector <pi>
//#define fin cin
//#define fout cout
int n,m;
int dist[MAXN];
vi d[MAXN];
int viz[MAXN];
int main(){
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin >> n >> m;
    for (int i = 1; i <= m; i++){
        int x,y,z;
        fin >> x >> y >> z;
        pi lol;
        lol=mp(y,z);
        d[x].pb(lol);
    }
    dist[1] = 0;
    for (int i = 2; i <= n; i++)
        dist[i] = INF;
    queue <int> q;
    q.push(1);
    while (!q.empty()){
        int node = q.front();
        viz[node] = 0;
        q.pop();
        for (auto i : d[node])
        if (dist[i.F] > dist[node] + i.S){
            dist[i.F] = dist[node] + i.S;
            if (!viz[i.F]){
                viz[i.F] = 1;
                q.push(i.F);
            }
        }
    }
    for (int i = 2; i <= n; i++){
        if (dist[i] < INF) fout << dist[i] << ' ';
        else fout << 0 << ' ';
    }
}