#include <bits/stdc++.h>
using namespace std;

#define N_MAX 50000 + 1

vector<vector<pair<int, int> > > graph(N_MAX, vector<pair<int, int> > (0));
vector<int> d(N_MAX, INT_MAX);
vector<bool> visited(N_MAX, false);


priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> >> Queue;

void dijkstra(int startNode){
    d.at(startNode) = 0;
    Queue.push(make_pair(d.at(startNode), startNode));

    int node, dist;
    while(!Queue.empty()){
        node = Queue.top().second;
        visited.at(node) = true;

        Queue.pop();

        for(auto& neighbour:graph.at(node)){
            dist = d.at(node)+neighbour.second;
            if( dist < d.at(neighbour.first)){
                d.at(neighbour.first) = dist;
                if(!visited.at(neighbour.first)){
                    Queue.push(make_pair(d.at(neighbour.first), neighbour.first));
                }
            }
        }
    }
}

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

    int n, m;
    fin>>n>>m;

    int x, y, c;

    for(auto i=1; i<=m; i++){
        fin>>x>>y>>c;
        graph.at(x).push_back(make_pair(y, c));
    }

    dijkstra(1);

    for(auto i=2; i<=n; i++) fout<<(d.at(i)==INT_MAX? 0:d.at(i))<<" ";
}