#include<iostream>
#include<fstream>
#include<vector>
#include<limits.h>
using namespace std;
struct nod{
int value;
vector<int> next;
vector<int> dist;};
nod*nnod(){
nod*dummy;
dummy=new nod;
dummy->value=INT_MAX;
return dummy;}
vector<nod*> graf;
class heap{
public:
    int n;
    vector<int> v;
    heap(int lng);
    void insert(int value);
    int min();
    int size();
private:
    int parent(int pos);
    int l_child(int pos);
    int r_child(int pos);
    void swap(int a,int b);
    void relax();
    bool isleaf(int pos);
    bool exist(int pos);
};
heap::heap(int lng){
    n=0;
    v.resize(lng,0);}
void heap::insert(int value){
    int i;
    v[n]=value;
    n++;
    i=n;
    while(exist(parent(i))&&graf[v[parent(i)]]->value>graf[v[i]]->value){
        swap(v[parent(i)],v[i]);
        i=parent(i);}}
int heap::min(){
    if(n>0){
        swap(v[0],v[n-1]);
        n--;}
    if(n!=0)relax();
    return v[n];}
int heap::size(){
return n;}
int heap::parent(int pos){
return (int)((pos-1)/2);}
int heap::l_child(int pos){
return pos*2+1;}
int heap::r_child(int pos){
return pos*2+2;}
void heap::swap(int a,int b){
int x=a;
a=b;b=x;}
void heap::relax(){
    int i,j;
    i=0;
    while(!isleaf(i)){
        j=l_child(i);
        if(exist(r_child(i))&&graf[v[r_child(i)]]->value<graf[v[j]]->value)j=r_child(i);
        if(graf[v[i]]->value<graf[v[j]]->value)return;
        swap(v[i],v[j]);
        i=j;}}
bool heap::isleaf(int pos){
return (!exist(l_child(pos))&&!exist(r_child(pos)));}
bool heap::exist(int pos){
return pos<n;}
void dijkstra(heap*h){
    int i=0;
    graf[0]->value=0;
    h->insert(0);
    while(h->size()!=0){
        i=h->min();
        for(int j=0;j<graf[i]->next.size();j++){
            if(graf[graf[i]->next[j]]->value>graf[i]->value+graf[i]->dist[j])graf[graf[i]->next[j]]->value=graf[i]->value+graf[i]->dist[j];
            h->insert(graf[i]->next[j]);}}}
int main(){
    int n,m,a,b,c;
    heap*h;
    ifstream f("dijkstra.in");
    f>>n>>m;
    h=new heap(n);
    for(int i=0;i<n;i++)graf.push_back(nnod());
    for(int i=0;i<m;i++){
        f>>a>>b>>c;
        graf[a-1]->next.push_back(b-1);
        graf[a-1]->dist.push_back(c);}
    f.close();
    dijkstra(h);
    ofstream g("dijkstra.out");
    for(int i=1;i<n;i++)g<<graf[i]->value<<' ';
    g.close();
return 0;}