#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct ura
{
    int varf,cost;
};

int v[50001], h[50001], poz[50001];

int n,nh,m;

vector <ura> s[50001];

void schimba(int x, int y)
{
    swap(h[x],h[y]);
    poz[h[x]]=x;
    poz[h[y]]=y;
}

void urca(int p)
{
    while(p>1 && v[h[p]]<v[h[p/2]]){
        schimba(p,p/2);
        p/=2;
    }
}

void coborare(int p)
{
    int fs,fd,bun;
    fs=2*p;
    fd=2*p+1;
    bun=p;
    if(fs<=nh && v[h[fs]]<v[h[bun]])
        bun=fs;
    if(fd<=nh && v[h[fd]]<v[h[bun]])
        bun=fd;
    if(bun!=p){
        schimba(p,bun);
        coborare(bun);
    }
}

void sterge(int p)
{
    if(p==nh)
        nh--;
    else{
        schimba(p,nh);
        poz[h[nh--]]=-1;
        urca(p);
        coborare(p);
    }
}

void prelucrare(int x)
{
    for(int i=1;i<=n;i++){
        v[i]=1000000001;
        h[++nh]=i;
        poz[i]=nh;
    }
    v[x]=0;
    while(nh>0){
        int val;
        val=h[1];
        sterge(1);
        for(auto p:s[val]){
            int y,c;
            y=p.varf;
            c=p.cost;
            if(v[val]+c<v[y]){
                v[y]=v[val]+c;
                urca(poz[y]);
            }
        }
    }
}

int main()
{
    in>>n>>m;
    for(int i=0;i<m;i++){
        int x,y,c;
        in>>x>>y>>c;
        s[x].push_back((ura){y,c});
    }
    prelucrare(1);
    for(int i=2;i<=n;i++)
        if(v[i]!=1000000001)
            out<<v[i]<<' ';
        else
            out<<0<<' ';
    return 0;
}