#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <string.h>

using namespace std;

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


struct nod{
    int v;
    int cost;
    nod(int a_v, int a_cost){
        v=a_v;
        cost=a_cost;
    }
    bool operator<(const nod& other)const{
        if(cost !=other.cost)
            return cost<other.cost;
        return v<other.v;
    }
};

int n,m;
int dist[50005];
vector<nod>adj[250005];
bool esteSet[50005];
set<nod>S;


void citire(){
    f>>n>>m;
    int x, y, c;
    for(int i=0; i<m; i++){
        f>>x>>y>>c;
        adj[x-1].emplace_back(y-1,c);
    }
    memset(dist,11, sizeof(dist));
}

void rezolvare(){
    S.insert(nod(0,0));
    dist[0]=0;
    esteSet[0]=0;
    while (!S.empty()){
        nod a_node= *S.begin();
        esteSet[a_node.v]= false;
        S.erase(S.begin());
        for (auto &v:adj[a_node.v]){
            if(dist[a_node.v] + v.cost < dist[v.v]){
                if(esteSet[v.v]){
                    S.erase(S.find(nod(v.v,dist[v.v])));
                    esteSet[v.v]=false;
                }
                dist[v.v]=dist[a_node.v] + v.cost;
                S.insert(nod(v.v,dist[v.v]));
                esteSet[v.v]= true;
            }
        }
    }
}

int main() {
    citire();
    rezolvare();
        for(int i=1; i<n; i++){
        if(dist[i]==185273099)
            g<<0<<" ";
        else
            g<<dist[i]<<" ";
    }

    return 0;
}