#include<fstream>
#include<queue>
#define inf 50003
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct nod
{
    int y;
    int cost;
    nod *urm;
};
nod *a[inf];
int D[inf];
int n,m;
class compara
{
    public:
    bool operator () (nod &i, nod &j)
    {
        return (i.cost > j.cost);
    }
};
priority_queue<nod,vector<nod>, compara> q;
void adauga(int i, int j, int c)
{
    nod *p=new nod;
    p->y=j;
    p->cost=c;
    p->urm=a[i];
    a[i]=p;
}
void dijkstra(int r)
{
    nod *p, u,v;
    D[r]=0;
    u.y=r;
    u.cost=0;
    q.push(u);
    while(q.size())
    {
        u=q.top();
        p=a[u.y];
        q.pop();
        if(D[u.y]<u.cost)
            continue;
        while (p)
        {
            if (u.cost+ p->cost < D[p->y])
            {
                D[p->y] = u.cost + p->cost;
                v.y = p->y;
                v.cost = D[p->y];
                q.push(v);
            }
            p = p->urm;
        }
    }
}
int main()
{
    int i,j,c;
    f>>n>>m;
    for(int k=1; k<=m;k++)
    {
        f>>i>>j>>c;
        adauga(i,j,c);

    }
    for(i=1;i<=n;i++)
       D[i]=1<<30;
   dijkstra(1);
   for(i=2;i<=n;i++)
    if(D[i]!=(1<<30))
    g<<D[i]<<" ";
else
    g<<0<<" ";
    return 0;
}