#include<iostream>
#include<fstream>
#include<vector>
#include<set>
#define ii 250000000
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n,m,d[50005];
bool viz[50005];
struct fiu
{
    int v,cost;
};
struct distanta
{
    int v,d;
};
bool operator<(distanta d1, distanta d2)
{
    return d1.d<d2.d;
}
vector<fiu> v[50005];
vector<fiu>::iterator it;
multiset<distanta> D;
multiset<distanta>:: iterator itd;
int main()
{
    in>>n>>m;
    int i,a,b,x;
    fiu f;
    distanta dd;

    dd.v=1;
    dd.d=0;
    //D.insert(dd);
    d[1]=0;
    for(i=2;i<=n;i++)
    {
        dd.v=i;
        dd.d=ii;
        D.insert(dd);
        d[i]=ii;
    }

    for(i=1;i<=m;i++)
    {
        in>>a>>b>>x;
        if(a==1)
        for(itd=D.begin();itd!=D.end();++itd)
        if(itd->v==b)
        {
            dd.v=b;
            dd.d=x;
            D.erase(itd);
            D.insert(dd);
            d[b]=x;
        }
        f.v=b; f.cost=x;
        v[a].push_back(f);
    }
    x=1;
    viz[1]=1;
    int ok=1,m,k;
    while(ok)
    {
        if(!D.empty())
        {
            itd=D.begin();
            viz[itd->v]=1;
            for(it=v[itd->v].begin();it!=v[itd->v].end();++it)
            {
                if(d[it->v]> d[itd->v]+ it->cost)
                {
                    d[it->v]=d[itd->v]+ it->cost;
                    for(itd=D.begin();itd!=D.end();++itd)
                    if(itd->v==it->v)
                    {
                        dd.v=it->v;
                        dd.d=d[itd->v]+ it->cost;
                        D.erase(itd);
                        D.insert(dd);
                    }
                }
            }
            D.erase(*D.begin());
        }
        else ok=0;
    }
    for(i=2;i<=n;i++) if(d[i]<ii) out<<d[i]<<' '; else out<<0<<' ';
    out<<'\n';
}