#include <bitset>
#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;
FILE *f,*g;

int drum[50002];
class compar//imi introduce in coada nodurlle sortate crescator in functie de cost
{
public:
    bool operator() (int X, int Y)
    {
        return (drum[X]>drum[Y]);
    }
};

priority_queue <int, vector <int>,compar> q;
vector <pair <int,int> > nod[50002];//asta e ca o matrice dinamica care memoreaza pe fiecare pozitie cate o ^structura^
//pair <int,int> e ca un fel de structura
bool viz[50002];

int main()
{
    int m,n,i,j,x,y,c,no,dist,cost,vecin;
    f=fopen("dijkstra.in","r");
    g=fopen("dijkstra.out","w");
    fscanf(f,"%d %d",&n,&m);
    for(i=1;i<=m;++i)
    {
        fscanf(f,"%d %d %d",&x,&y,&c);
        nod[x].push_back({y,c});//la fiecare nod introducem vecinii si costul fiecarui drum
    }
    for(i=2;i<=n;++i)//eu am nevoie de drumul de cost cel mai mic posibil
        drum[i]=2000000000;
    q.push(1);
    while(!q.empty())
    {
        no=q.top();//primul element din coada
        q.pop();
        if(!viz[no])//nu am mai trecut prin nodul acesta
        {
            for(i=0;i<nod[no].size();++i)
            {
                vecin=nod[no][i].first;//vecinul nodului no
                cost=nod[no][i].second;//costul dintre nodul no si nodul i
                dist=drum[no]+cost;//costul pana la nodul no
                if(dist<drum[vecin])
                {
                    drum[vecin]=dist;
                    q.push({vecin});
                }
            }
        }
        viz[no]=1;
    }
    for(i=2;i<=n;++i)
    {
        if(drum[i]==2000000000)
            fprintf(g,"0 ");
        else
            fprintf(g,"%d ",drum[i]);
    }
    fclose(f);
    fclose(g);
    return 0;
}