#include <iostream>
#include <fstream>
#include <list>
#include <stdio.h>
#include <queue>
#include <stdio.h>

using namespace std;

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

struct item
{
    int val,to;
};
typedef list<item> INT_LIST;
typedef list<int> NODES_LIST;
typedef list<item>::iterator iter;

void print(NODES_LIST &nodes)
{
    for(list<int>::iterator it=nodes.begin();it!=nodes.end();it++)
        cout<<(*it)<<" ";
    cout<<endl;
}
void dijkstra(INT_LIST *a, int *b, int n, NODES_LIST &nodes)
{
    while(!nodes.empty())
    {
        NODES_LIST tmp;
        int curr = nodes.back();
        //print(nodes);
        //cout<<"-> "<<curr<<endl;
        for(iter it=a[curr].begin();it!=a[curr].end();it++)
        {
            int to = (*it).to;
            int val = (*it).val;
            //cout<<from<<" -> "<<to<<" : "<<val<<endl;
            if(b[curr]+val < b[to])
            {
                b[to] = b[curr]+val;
                nodes.push_front(to);
            }
        }
        nodes.pop_back();
    }

}
int main()
{
    FILE *f = fopen("dijkstra.in","r");
    // Initialization
    int n,m;
    fscanf(f,"%d %d",&n,&m);
    INT_LIST *a = new INT_LIST[n+2];
    int *b = new int[n+2];
    fill(b,b+n+2,99999);
    NODES_LIST nodes;

    for(int i=1;i<=m;i++)
    {
        int from,to,val;
        //fin>>from>>to>>val;
        fscanf(f,"%d %d %d",&from,&to,&val);
        item curr;
        curr.to = to;
        curr.val = val;
        a[from].push_front(curr);
        //curr.to = from;
        //a[to].push_front(curr);
    }

nodes.push_back(1);
b[1] = 0;
dijkstra(a,b,n,nodes);
for(int i=2;i<=n;i++) if(b[i]!=99999) fout<<b[i]<<" "; else fout<<"0 ";
}