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



ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct compare{
    bool operator()(const pair<int,int> &a, const pair<int,int> &b){
        return a.second>b.second; //compar dupa cost
    }
};

vector<pair<int,int>> v[50001]; //de ex 1: (2,3) unde 3 este costul
priority_queue<pair<int,int>,vector<pair<int,int>>,compare>heap;
int n,m,x,y,cost;
int dist[50001],viz[50001];

void add(int node1,int node2,int cost){
    v[node1].push_back(make_pair(node2,cost));
}

void dijkstra(int node){
    viz[node]=1;

    for(int i=0;i<v[node].size();i++){
        if(viz[v[node][i].first]==0) //parcurg lista de adiacenta si vad daca a fost vizitat fiecare nod
//bag in heap (u,v,cost(u,v))
        {

            heap.push(make_pair(v[node][i].first,v[node][i].second+dist[node]));


        }
    }
    while(heap.size()!=0){
        pair<int,int> top;
        top=heap.top();
        heap.pop();

        if(viz[top.first]== 0) //u e in apm, dar v nu
        {
            dist[top.first]=top.second;
            dijkstra(top.first);
        }

    }

}


int main() {

    f>>n>>m;
    for(int i=0;i<m;i++){
        f>>x>>y>>cost;
        add(x,y,cost);
    }
    for(int i=0;i<n;i++){
        dist[i]=0;
    }
    dijkstra(1);
    for(int i=2;i<=n;i++){
        g<<dist[i]<<" ";
    }

}