#include <bits/stdc++.h>
#define NMAX 50002
#define INF 999999999

using namespace std;

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

int N, M;

vector <int> Ad[NMAX];
vector <int> Cost[NMAX];
int dist[NMAX];
bool vis[NMAX];

priority_queue <pair<int,int>, vector<pair<int,int> >, greater<pair<int, int>>> pq;
int main()
{

    fin >> N >> M;
    for(int i = 1; i <= M; ++i){
        int a, b, d;
        fin >> a >> b >> d;
        Ad[a].push_back(b);
        Cost[a].push_back(d);
    }

	 for(int i = 1; i <= N; ++i)
        dist[i] = INF;

    dist[1] = 0;
    pq.push({0, 1});

    while(!pq.empty()){
        int u, w;
        u = pq.top().second;
        pq.pop();

        if(vis[u])
            continue;
        else
            vis[u] = 1;


        for(int i = 0; i < Ad[u].size(); ++i){
            w = Ad[u][i];
            if(dist[w] > dist[u] + Cost[u][i]){
                dist[w] = dist[u] + Cost[u][i];
                pq.push({dist[w], w});
            }
        }
    }

    for(int i = 2; i <= N; ++i)
        if (dist[i] == INF)
            fout << "0 ";
        else
            fout << dist[i] << ' ';


    return 0;
}