#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#include <cstring>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int inf=0x3f3f3f3f;
int Rlcost[50001];
struct graf
{
    int y,cost;
};
vector<graf>v[50001];
vector<graf>::iterator it;
struct cod
{
    int nod,cost;
};
struct comp
{
    bool operator() (const cod &a,const cod &b)
    {
        return a.cost>b.cost;
    }
};
priority_queue<cod,vector<cod>,comp> H;
inline void dijkstra(int i)
{
    for(it=v[i].begin();it!=v[i].end();it++)
    {
        int a=it->y;
        if(it->cost+Rlcost[i]<Rlcost[a])
        {
            cod pas;
            pas.nod=a;
            pas.cost=it->cost+Rlcost[i];
            Rlcost[a]=pas.cost;
            H.push(pas);
        }
    }
    H.pop();
}
int main()
{
    memset(Rlcost,inf,sizeof(Rlcost));
    int n,q,m,i;
    graf pas;
    fin>>n>>m;
    for(q=1;q<=m;q++)
    {
        fin>>i>>pas.y>>pas.cost;
        v[i].push_back(pas);
    }
    cod rac;
    for(it=v[1].begin();it!=v[1].end();it++)
    {
        rac.nod=it->y;
        rac.cost=it->cost;
        H.push(rac);
        Rlcost[it->y]=rac.cost;
    }
    while(!H.empty())
    {
        while(H.top().cost!=Rlcost[H.top().nod]) H.pop();
        i=H.top().nod;
        dijkstra(i);
    }
    for(i=2;i<=n;i++)
    {
        if(Rlcost[i]==inf) fout<<"0 ";
        else fout<<Rlcost[i]<<" ";
    }
}