#include<fstream>
#include<vector>
#include<queue>
#define mp make_pair
#define pb push_back
#define NMAX 50000
#define MAX (1<<30)
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n,m,A,B,nc,d[NMAX];
short C;
bool viz[NMAX];
vector<pair<int,short> >v[NMAX];
struct minimum
{
    bool operator()(int A, int B)
    {
        return d[A] > d[B];
    }
};
priority_queue<int,vector<int>,minimum> q;
void citire()
{
    in>>n>>m;
    for(int i=0;i<m;i++)
    {
        in>>A>>B>>C;
        v[A].pb(mp(B,C));
    }
}
void prelucrare()//ns==nod_start
{
    for(int i=2;i<=n;i++)
        {
            d[i]=MAX;//MAX==infinit
            viz[i]=0;//viz==vizitat
        }
    d[1]=0;
    q.push(1);
    viz[1]=1;
    while(!q.empty())
    {
        nc=q.top();//nodul curent
        q.pop();
        for(unsigned i=0;i<v[nc].size();i++)
            if(d[nc]+v[nc][i].second<d[v[nc][i].first])
        {
            d[v[nc][i].first]=d[nc]+v[nc][i].second;
            if(!viz[v[nc][i].first])
            {
                q.push(v[nc][i].first);
                viz[v[nc][i].first]=1;
            }
        }
    }

}
void tipar()
{
    for(int i=2;i<=n;i++)
        if(d[i]==MAX)
            out<<0<<" ";
        else
            out<<d[i]<<" ";
}
int main()
{
    citire();
    prelucrare();
    tipar();
}