/*Acest algoritm determina drumurile de cost minim del
la un nod la toate celelate.
Graful este orientat!*/
#include<iostream>
#include<cstdio>
#include<vector>
#include<list>
#define Inf 15000
#define Nmax 100

using namespace std;

typedef vector<size_t> linie;
vector<linie> c;
vector<size_t> tata,d;
size_t m,n;
void dijkstra(int);
void drum(int,int);

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdin);
    cin>>n>>m;
    int i,j,x,y,k;
    c.resize(n+1);
    for(i=1;i<=n;i++) c[i].resize(n+1,Inf);
    for(i=1;i<=m;i++)
    {
        cin>>x>>y>>k;
        c[x][y]=k;
    }
    dijkstra(1);
    for(i=2;i<=n;i++) cout<<d[i]<<" ";

}

void dijkstra(int nod)
{
    int i,j,Min,k;
    vector<bool> viz; viz.resize(n+1,0);
    d=c[nod];
    viz[nod]=1;
    tata.resize(n+1,nod);tata[nod]=0;
    while(1)
    {
        Min=Inf;
        for(i=1;i<=n;i++)
            if(!viz[i]&&d[i]<Min)
            {
                Min=d[i];
                k=i;
            }
        //actualizam distantele
        if(Min!=Inf)
        {
            viz[k]=1;
            for(i=1;i<=n;i++)
            if(d[i]>d[k]+c[k][i])
            {
                d[i]=d[k]+c[k][i];
                tata[i]=k;
            }
        }
        else break;
    }

}
 void drum(int x,int y)
 {
    dijkstra(x);
    list<int> drum;
    do
    {
        drum.push_front(y);
        y=tata[y];
    }
    while(y);
    while(drum.size())
    {
        printf("%d ",drum.front());
        drum.pop_front();
    }
 }