#include <bits/stdc++.h>
#define NMAX 50005

using namespace std;

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

int N, M;
vector < pair <int, int> > g[NMAX];
int dist[NMAX];
bool in_coada[NMAX];

struct cmp{
    bool operator()(int x, int y){
        return dist[x] > dist[y];
    }
};

priority_queue < int, vector < int >, cmp> q;

void dijkstra(int start){
    q.push(start);
    dist[start] = 0;
    in_coada[start] = true;

    for(int i = 2; i <= N; i++)
        dist[i] = INT_MAX;

    while(!q.empty()){
        int nod_curent = q.top();

        for(size_t i = 0; i < g[nod_curent].size(); i++){
            // g[nod_curent][i].first => Nodul
            // g[nod_curent][i].second => Costul

            if(dist[nod_curent] + g[nod_curent][i].second < dist[g[nod_curent][i].first]){
                dist[g[nod_curent][i].first] = dist[nod_curent] + g[nod_curent][i].second;
                if(!in_coada[g[nod_curent][i].first]){
                    in_coada[g[nod_curent][i].first] = true;
                    q.push(g[nod_curent][i].first);
                }
            }
        }

        q.pop();
        in_coada[nod_curent] = false;
    }
}

int main(){
    int i, x, y, c;

    fin >> N >> M;

    for(int i = 0; i < M; i++)
    {
        fin >> x >> y >> c;
        g[x].push_back(make_pair(y, c));
    }

    dijkstra(1);

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

    return 0;
}