#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50005
#define inf 2e9
using namespace std;

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

struct State{
    int node, cost;

    bool operator< (const State& other) const {
        return cost > other.cost;
    }
};

//vector < vector < pair < int, int > > > nod;
vector < pair < int, int > > nod[NMAX];
priority_queue < State > q;

int n, m, best_path[NMAX];

void read(){
    int x, y, cost;
    fin>>n>>m;
    for(int i = 1; i <= m; ++i){
         fin>>x>>y>>cost;
         nod[x].push_back({y, cost});
    }
    for(int i = 1; i <= n; ++i)
        best_path[i] = inf;
}

void dijkstra(int source){
    int node, cost;
    best_path[source] = 0;
    q.push({source, 0});
    while(!q.empty()){
        node = q.top().node;
        cost = q.top().cost;
        q.pop();
        if(best_path[node] < cost)
            continue;
        for(auto it: nod[node]){
            int neighbour = it.first;
            int edge_cost = it.second;
            if(best_path[neighbour] > cost + edge_cost){
                best_path[neighbour] = cost + edge_cost;
                q.push({neighbour, best_path[neighbour]});
            }
        }
    }
}

void print(){
    for(int i = 2; i <= n; ++i){
        if(best_path[i] == inf)
            fout<<0<<' ';
        else
            fout<<best_path[i]<<' ';
    }
}

int main()
{
    read();
    dijkstra(1);
    print();
    return 0;
}