#include <bits/stdc++.h>
using namespace std;

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

const int N_MAX = 1000 + 5;
const int INF = INT_MAX/100 - 100000;

bool expandat [N_MAX];
int cost [N_MAX];
int ne_expandat = 0 , c,a,b, n,m;
set<pair<int,int> > vf;
int gr [N_MAX][N_MAX];

void citire();

int main()
{
    citire();

    vf.insert({0,1});
    cost[1] = 0;
    ne_expandat = n;
bool    am_de_exp = 1;

    while(ne_expandat && am_de_exp){

        //cout<<ne_expandat<<vf.size()<<endl;

        am_de_exp = false;

        for(auto i:vf){
            if(!expandat[i.second]){
                am_de_exp = true;
                bool gasit = false;
                expandat[i.second] = 1;
                ne_expandat --;
                for(int vecin = 1; vecin<=n; vecin++){
                   // cout<<i.first<<vecin<<" "<< gr[i.second][vecin]<<endl;
                    if(i.first + gr[i.second][vecin] < cost[vecin]){
                        vf.erase({cost[vecin],vecin});
                        cost[vecin] = cost[i.second] + gr[i.second][vecin];
                        vf.insert({cost[vecin],vecin});
                        gasit = true;
                    }
                }

                if(gasit)
                    break;

            }
        }

    }

    for(int i = 2; i<=n; ++i){
        if(cost[i] != INF)
        fout<<cost[i]<<" ";
        else fout<<"0 ";
    }

    return 0;
}


void citire(){

      fin>>n>>m;

    for(int i = 1; i<=n; i++)
        for(int j = 1; j<=n; j++)
            gr[i][j] = INF;

    for(int i = 1; i<=n; ++i)
            cost[i] = INF;


    for(int i = 1; i<=m; ++i){
        fin>>a>>b>>c;
        gr[a][b] = c;
    }

}