#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];//in a retinem muchiile si costul lor a[i].y=intre nodurile i si y eyista muchie ce are costul a[i].cost
int D[inf];//in D[]retinem drumurile;D[i]=drumul minim de la radacina la i
int n,m;//n-nr de noduri, m-nr de muchii
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;
        }
    }
}
/*void dijkstra(int s)
{
    nod *p, temp, temp_1;

    D[s] = 0;
    temp.y = s;
    temp.cost = 0;
    q.push(temp);
    while (q.size())
    {
        temp = q.top();
        p = a[temp.y];
        q.pop();

        if (D[temp.y] < temp.cost)
            continue;

        while (p)
        {
            if (temp.cost + p->cost < D[p->y])
            {
                D[p->y] = temp.cost + p->cost;
                temp_1.y = p->y;
                temp_1.cost = D[p->y];
                q.push(temp_1);
            }
            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;
}