#include <iostream>
#include <cstdio>
#define inf 1073741824
#include <set>
#include <vector>
using namespace std;

set <pair<int,int>> v;
vector <pair<int,int> > lv[50001];
int d[50001],t[50001],viz[50001];

int main()
{
    FILE *f=fopen("dijkstra.in","r");
    int n,m,i,x,y,cost,nodc,dmin;
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&cost);
        lv[x].push_back(make_pair(y,cost));
    }
    for(i=1;i<=n;i++)t[i]=d[i]=inf;
    d[1]=t[1]=0;
    v.insert(make_pair(0,1));
    while(!v.empty())
    {
        dmin=v.begin()->first;
        nodc=v.begin()->second;viz[nodc]=1;
        v.erase(v.begin());
        for(auto &nod:lv[nodc])
            if(!viz[nod.first] && dmin+nod.second < d[nod.first])
            {
                v.erase(make_pair(d[nod.first],nod.first));
                d[nod.first]=dmin+nod.second;
                t[nod.first]=nodc;
                v.insert(make_pair(d[nod.first],nod.first));
            }
    }
    f=fopen("dijkstra.out","w");
    for(i=2;i<=n;i++)
        fprintf(f,"%d ",(d[i]==inf?0:d[i]));
    return 0;
}