#include<fstream>
#include <iostream>
#include<list>
#include<string>

using namespace std;

#define INF 32000
#define min(a,b) ((a<b)?a:b)

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

int n,m,start,end,c;
int *viz,*dr,*par;

struct lvertex
{
    int v;
    int c;
};

list<lvertex> *listd;

int getCostAt(list<lvertex> l,int v)
{
    for(list<lvertex>::iterator it=l.begin();it!=l.end();it++)
    {
        if((*it).v==v)
            return (*it).c;
    }
    return INF;
}

void citire()
{
    fin>>n>>m;   
   
    viz=new int[n+1];
    dr=new int[n+1];
    par=new int[n+1];
   
    memset(viz,0,(n+1)*sizeof(int));
    memset(dr,0,(n+1)*sizeof(int));
    memset(par,0,(n+1)*sizeof(int));
   
    listd=new list<lvertex>[n+1];
   
    int x,y,c;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        lvertex k;
        k.v=y;
        k.c=c;
        listd[x].push_back(k);
        //k.v=x;
        //listd[y].push_back(k);
    }
   
    for(int i=1;i<=n;i++) dr[i]=INF;
   
    fin.close();
}

void rezolva()
{
    viz[start]=1;
    par[start]=0;
    for(list<lvertex>::iterator it=listd[start].begin();it!=listd[start].end();it++)
    {
        par[(*it).v]=1;
        dr[(*it).v]=(*it).c;
    }
   
    int ok=1,drmin;
    while(ok)
    {
        drmin=INF;
        int poz=-1;
        for(int i=1;i<=n;i++)
            if(drmin>dr[i] && !viz[i])
            {
                drmin=dr[i];
                poz=i;
            }
        if(drmin==INF)
            ok=0;
        else
        {
            viz[poz]=1;
            for(int i=1;i<=n;i++){
                int temp=getCostAt(listd[poz],i);
                if(!viz[i] && temp!=INF)
                {
                    int aux=dr[poz]+temp;
                    if(dr[i]>aux){
                        dr[i]=aux;
                        par[i]=poz;
                    }
                }
            }
        }
    }
}

void afisrec(int v)
{
    if(v>1)
    {
        afisrec(par[v]);
        cout<<v<<" ";
		c+=dr[v];
    }
}

void afiseaza()
{
    afisrec(end);
    fout.close();
}

int main()
{	int v;
    citire();
	start=1;
	end=n;
	//for (end=2; end<=n; end++) {
		rezolva();
		//afiseaza();
		for (int i=2; i<=n; i++)
			fout<<dr[i]<<" ";
	//}
    return 0;
}