#include <iostream>
#include <fstream>
#include <vector>
#define inf 999999
using namespace std;

int n, m;
vector<vector<int> > c;
vector<int> l;
vector<int> tata;
vector<bool> v;
void citire(){
    ifstream f("dijkstra.in");
    f>>n>>m;
    v=vector<bool>(n+1, false);
    l=vector<int>(n+1, inf);
    tata=vector<int>(n+1, -1);
    c=vector<vector<int> >(n+1, vector<int>(n+1, inf));
    for(int i=1;i<=n;i++)
        c[i][i]=-1;

    int x,y,z;
    for(int i=0;i<m;i++){
        f>>x>>y>>z;
        c[x][y]=z;
    }

    return;
    for(int i=1;i<=n;i++)
        cout<<"\t"<<i;
    cout<<"\n";
    for(int i=1;i<=n;i++){
        cout<<i<<":\t";
        for(int j=1;j<=n;j++)
            cout<<c[i][j]<<"\t";
        cout<<"\n";
    }

}
void dijkstra(int x0){
    int minim, k, ok;
    tata[x0]=0;
    v[x0]=true;
    for(int i=1;i<=n;i++)
        l[i]=c[x0][i];
    ok=1;
    while(ok){
        minim=inf;
        for(int i=1;i<=n;i++)
            if(!v[i] && minim>l[i])
                minim=l[i], k=i;
        if(minim != inf){
            v[k]=true;
            for(int i=1; i<=n; i++)
                if(!v[i] && l[i]>l[k]+c[k][i]){
                    l[i]=l[k]+c[k][i];
                    tata[i]=k;
                }
        }
        else ok=0;
    }
}
int main()
{
    citire();
    dijkstra(1);
    ofstream g("dijkstra.out");
    for(int i=2;i<=n;i++)
        //cout<<1<<"->"<<i<<"="<<l[i]<<"\n",
        g<<l[i]<<" ";
    return 0;
}