#include <fstream>
#include <vector>
#include <set>
#define inf 100000001
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
vector <pair<int,int> > L[50001];
set <pair<int,int> > s;
int n,m,i,j,x,y,c,d[50001],cost,nodv;
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>c;
        L[x].push_back(make_pair(y,c));
    }
    for(i=2;i<=n;i++)
        d[i]=inf;
    s.insert(make_pair(0,1));
    while(!s.empty()){
        x=s.begin()->second;
        s.erase(s.begin());
        for(vector <pair<int,int> >::iterator it=L[x].begin();it!=L[x].end();it++){
            nodv=it->first;
            cost=it->second;
            if(d[nodv]>d[x]+cost){
                s.erase(make_pair(d[nodv],nodv));
                d[nodv]=d[x]+cost;
                s.insert(make_pair(d[nodv],nodv));
            }
        }
    }
    for(i=2;i<=n;i++){
        if(d[i]==inf){
            fout<<"0 ";
        }
        else
            fout<<d[i]<<" ";
    }
}