#include <stdio.h>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
FILE *f,*g;
int n,m;
int drum[50015];
bool viz[50015];
vector <pair <int,int> >graf[50015];
struct Nod
{
    int v,c;
};
struct compara///functia asta e un criteriu de plasare a elementelor in coada
{
    bool operator()(Nod x,Nod y)///deoarece avem nevoie de DRUMUL MINIM
    {
        return x.c>y.c;
    }
};
priority_queue<Nod, vector<Nod>,compara> coada;

void dijkstra()
{
    coada.push({1,0});
    int nod,cost,vecin,drm;
    viz[1]=false;
    for(int i=1;i<=n;i++)
        drum[i]=99999999;
    drum[1]=0;
    while(!coada.empty())
    {
       nod=coada.top().v;
       drm=coada.top().c;
       coada.pop();
       if(viz[nod]==false)
       {
          for(size_t i=0;i<graf[nod].size();i++)
          {
             vecin=graf[nod][i].first;
             cost=graf[nod][i].second;
             if(drm+cost<drum[vecin])
             {
                 drum[vecin]=drm+cost;
                 coada.push({vecin,drum[vecin]});
             }
          }
       }
       viz[nod]=true;
    }
}
void read()
{
    int x,y,c;
    fscanf(f,"%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        fscanf(f,"%d %d %d",&x,&y,&c);
        graf[x].push_back(make_pair(y,c));
    }
}
int main()
{
    f=fopen("dijkstra.in","r");
    g=fopen("dijkstra.out","w");

    read();

    dijkstra();

    for(int i=2;i<=n;i++)
        if(drum[i]!=99999999)
            fprintf(g,"%d ",drum[i]);
        else
            fprintf(g,"0 ");
    return 0;
}