#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define nmax 50005
#define Inf 1000000000
using namespace std;

int n,m,startNode;
struct muchie{
unsigned short int y;int c;
}auxM, vec;

struct elemCoada{
int i, val;
}auxEl;

struct comp{
bool operator()(elemCoada &a, elemCoada &b){
    return a.val > b.val;
}};

priority_queue<int, vector<elemCoada>, comp> d;
vector< vector<muchie> > A;
vector<muchie> aux;
vector<int> dOptima;


void initializare()
{
    int x,y,c;
    cin>>n>>m;
    A.resize(n+1);
    dOptima.assign(n+2,Inf);    dOptima[startNode]=0;

    for(int i=1;i<=m;i++){
        scanf("%d%d%d", &x, &y, &c);
        auxM.y=y;
        auxM.c=c;
        A[x].push_back(auxM);

        if(x==startNode){
            auxEl.i=y;
            auxEl.val=c;
            d.push(auxEl);
            dOptima[y]=c;
        }
    }
}

void Dijkstra()
{
    int nrDistRez;
    elemCoada nOptim;
    vector<bool> viz(n+1);
    viz[startNode]=1;
    nrDistRez=1;
    do
    {
        if( !d.empty() ){
            nOptim=d.top();
            d.pop();
            nrDistRez++;
            //pentru fiecare nod pentru care exista muchie din nOptim in acel nod
            for(int i=0; i<A[nOptim.i].size(); i++){
                vec = A[nOptim.i][i];
                //daca putem imbunatati costul drumului din nodStart in vecinul nodului optim prin nOptim
                if( dOptima[vec.y] > dOptima[nOptim.i] + vec.c){
                    // imbunatateste drumul
                    dOptima[vec.y] = dOptima[nOptim.i] + vec.c;
                    // adauga vecinul in coada cu prioritate
                    auxEl.i=vec.y;
                    auxEl.val=dOptima[vec.y];
                    d.push(auxEl);
                    }
            }
        }
    }   //cat timp mai sunt noduri in coada cu prioritate si nu am incercat imbunatatirea distantelor prin fiecare nod
    while(!(d.empty() || nrDistRez==n));

    for(int i=2; i<=n; i++)
        if(dOptima[i]==Inf)
            cout<<0<<' ';
        else
            cout<<dOptima[i]<<' ';
    cout<<'\n';
}

int main()
{
    freopen("dijkstra.in","rt",stdin);
    freopen("dijkstra.out","wt",stdout);
    startNode=1;
    initializare();
    Dijkstra();
}