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

using namespace std;
FILE *f,*g;

class compar
{
public:
    bool operator() (pair <int,int> X, pair <int,int> Y)
    {
        return (X.second > Y.second);
    }
};

priority_queue <pair <int,int>, vector <pair <int,int> >,compar> q;//imi introduce in coada nodurlle sortate crescator in functie de cost
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 drum[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=1;i<=n;++i)
        drum[i]=2000000000;
    drum[1]=0;
    q.push({1,0});
    while(!q.empty())
    {
        //in q.top().first e nodul si in q.top().second e costul
        no=q.top().first;
        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;
                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,nod[no][i].second});
                }
            }
        }
        viz[no]=1;
    }
    for(i=2;i<=n;++i)
    {
        if(drum[i]==2000000000)
            drum[i]=0;
        fprintf(g,"%d ",drum[i]);
    }
    fclose(f);
    fclose(g);
    return 0;
}