#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int N=50001,inf=1000000001;
vector <int> a[N],c[N];
int n,m,d[N],poz[N],h[N],nh;
void schimba(int p,int q)
{
    int aux=h[p];
    h[p]=h[q];
    h[q]=aux;
    poz[h[p]]=p;
    poz[h[q]]=q;
}

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

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

void sterge(int p)
{
    schimba(p,nh);
    nh--;
    urca(p);
    coboara(p);
}

void scrie()
{
    for (int i = 1; i <= nh; i++)
    {
        g << "(" << h[i] << "," << d[h[i]] << ") ";
    }
    g << "\n";
}

void dijkstra(int x0)
{
    nh=n;
    for(int i=1;i<=n;i++){
        d[i]=inf;
        h[i]=i;
        poz[i]=i;
    }
    d[x0]=0;
    urca(poz[x0]);
    while(nh>0 && d[h[1]]!=inf){
        //scrie();
        int x=h[1];
        sterge(1);
        for(int i=0;i<a[x].size();i++){
            int y=a[x][i];
            int cost=c[x][i];
            if(d[x]+cost<d[y]){
               d[y]=d[x]+cost;
               urca(poz[y]);
            }
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,cost;
        f>>x>>y>>cost;
        a[x].push_back(y);
        c[x].push_back(cost);
    }
    dijkstra(1);
    for(int i=2;i<=n;i++)
        g<<d[i]<<' ';
    return 0;
}