#include<fstream>
#include<iostream>
#include<set>
#include<vector>
using namespace std;
int N,M,r[50005],contor;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
set< pair<int,int> > s;
vector <int> v[50005],d[50005];
bool viz[50005];
int main()
{
    in>>N>>M;
    int i,a,b,c,min;
    for(i=1;i<=N;++i) v[i].push_back(0),d[i].push_back(0),r[i]=1<<30;
    r[1]=0;
    for(i=1;i<=M;++i)
    {
        in>>a>>b>>c;
        v[a].push_back(b);
        v[a][0]++;
        d[a].push_back(c);
        if(c<min) min=c;
    }
    s.insert(make_pair(0,1));
    contor=1;
    int dd,nn;
    while(contor)
    {
        dd=s.begin()->first;
        nn=s.begin()->second;
        if(viz[nn]) s.erase(s.begin()),contor--;
        else
        {
            viz[nn]=1;
            for(i=1;i<=v[nn][0];++i)
            {
                if(r[ v[nn][i] ] > r[nn] + d[nn][i] && !viz[v[nn][i]])
                {
                    s.erase( make_pair(r[ v[nn][i] ],v[nn][i]) );
                    r[ v[nn][i] ]= r[nn] + d[nn][i];
                    s.insert( make_pair(r[ v[nn][i] ],v[nn][i]) );
                    contor++;
                }
            }
        }
    }
    for(i=2;i<=N;++i)
    {
        if(r[i]< (1<<30)) out<<r[i]<<' ';
        else out<<"0 ";
    }
    out<<'\n';
}