#include <fstream>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;

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

const int NMAX=50050,inf=100000000;

int n,m;
int d[NMAX];
vector<pair<int,int> >lista[NMAX];
struct comparator{
    bool operator()(pair<int,int>a,pair<int,int>b){
        return a.second>b.second;
    }
};
priority_queue<pair<int,int>,vector<pair<int,int> >,comparator>q;
void citire()
{
    fin>>n>>m;
    int a,b,c;
    for (int i=1; i<=m; i++){
        fin>>a>>b>>c;
        lista[a].push_back(pair<int,int>(b,c));
    }
}
void dijkstra()
{
    for (int i=1; i<=n; i++)
        d[i]=inf;
    d[1]=0;
    q.push(pair<int,int>(1,0));
    pair<int,int> cont;
    while (!q.empty()){
        cont=q.top();
        q.pop();

        for (vector<pair<int,int> >::iterator it=lista[cont.first].begin(); it!=lista[cont.first].end(); it++){
            if (d[it->first]>d[cont.first]+it->second){
                //cout<<it->first<<' '<<d[it->first]<<'\n';
                d[it->first]=d[cont.first]+it->second;
                //cout<<it->first<<' '<<d[it->first]<<'\n';
                if (it->first==17){
                    fout<<"cucu";
                }
                q.push(pair<int,int>(it->first,d[it->first]));
            }
        }
    }
}
int main()
{
    citire();
    dijkstra();
    for (int i=2; i<=n; i++){
        if (d[i]==inf)
            d[i]=0;
        fout<<d[i]<<' ';
    }
    fout<<'\n';
    return 0;
}