#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX = 50001;
#define infinit 2e9
struct State {
    int node, cost;

    bool operator< (const State& other) const {
        /// State o sa fie integrat intr-un priority queue
        /// ne propunem sa construim un min-heap de state-uri
        return cost > other.cost;
    }
};

vector <pair<int, int>> graph[NMAX];
int best_dist[NMAX];
int n, m, cost;
priority_queue<State> pq;

void read() {
    int x, y;
    fin>>n>>m;
    for(int i=1;i<=n;i++){
        best_dist[i]=infinit;
    }
    for(int i = 1; i <= m; ++i){
        fin>>x>>y>>cost;
        graph[x].push_back({y, cost});
    }
}
void dijkstra(int source) {
    int node,cost;
    best_dist[source]=0;
    pq.push({source,0});
    while(!pq.empty())
    {
        node=pq.top().node;
        cost=pq.top().cost;
        pq.pop();
        /// range-based for-loop
        /// pentru fiecare 'neighbour' din graph[node]
        /// executa ...
        for (auto edge: graph[node]) {
            int neighbour = edge.first;
            int edge_cost = edge.second;
            if( best_dist[neighbour] > cost+edge_cost)
            {
                best_dist[neighbour]=cost+edge_cost;
                pq.push({neighbour,best_dist[neighbour]});
            }
        }
    }
}

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

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