#include<iostream>
#include<fstream>
#include<vector>
#include<list>
#include<limits.h>
using namespace std;
struct nod{
    int cost;
    int visited;
    int marked;
    vector<nod*> next;
    vector<int> dist;};
void dijkstra(vector<nod*> graf,nod* start){
    list<nod*> set;
    list<nod*>::iterator i_min;
    nod*cur;
    int min;
    for(int i=0;i<(int)graf.size();i++){graf[i]->cost=INT_MAX;graf[i]->visited=graf[i]->marked=0;}
    set.push_back(start);
    start->cost=0;
    while(!set.empty()){
        min=INT_MAX;
        for(list<nod*>::iterator it=set.begin();it!=set.end();it++)
        if((*it)->cost<min){min=(*it)->cost;cur=(*it);i_min=it;}
        cur->visited=1;
        set.erase(i_min);
        for(int i=0;i<(int)cur->next.size();i++)
        if(cur->dist[i]+cur->cost<cur->next[i]->cost){
            cur->next[i]->cost=cur->dist[i]+cur->cost;
            if(cur->next[i]->visited==0&&cur->next[i]->marked==0){
                set.push_back(cur->next[i]);
                cur->next[i]->marked=1;}}}}
int main(){
    int n,m,d1,d2,d3;
    vector<nod*> graf;
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    for(int i=0;i<n;i++)graf.push_back(new nod);
    for(int i=0;i<m;i++){
        f>>d1>>d2>>d3;
        graf[d1-1]->next.push_back(graf[d2-1]);
        graf[d1-1]->dist.push_back(d3);}
    dijkstra(graf,graf[0]);
    for(int i=1;i<n;i++)
    if(graf[i]->cost!=INT_MAX)g<<graf[i]->cost<<' ';
    elseg<<"0 ";
    f.close();g.close();
return 0;}