#include <iostream>
#include <fstream>
#include <queue>
#define inf 2000001
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct nod
{
    int info,cost;
    nod *urm;
};
nod *prim[50001];
int n,m;
int d[50001];
class ComparVf
{
    public:
    bool operator()(const int &x,const int &y)
    {
        return d[x]<d[y];
    }
};
priority_queue <int,vector<int>,ComparVf> H;
void add(nod *&prim,int x,int c)
{
    nod *p=new nod;
    p->info=x;
    p->cost=x;
    p->urm=prim;
    prim=p;
}
void Citire()
{
    int i,x,y,c;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        add(prim[x],y,c);
    }
}
void Dijkstra()
{
    int x,i;
    nod *p;
    for(i=1;i<=n;i++)
            d[i]=inf;
    d[1]=0;
    H.push(1);
    while(!H.empty())
    {
        x=H.top();
        H.pop();
        for(p=prim[x];p!=NULL;p=p->urm)
            if(d[x]+p->cost<d[p->info])
        {
            d[p->info]=d[x]+p->cost;
            H.push(p->info);
        }
    }
for(i=2;i<=n;i++)
    if(d[i]==inf)
        fout<<0<<" ";
    else
        fout<<d[i]<<" ";
}
int main()
{
    Citire();
    Dijkstra();
    return 0;
}