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

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

const int N_MAX = 5000 + 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;

    while(ne_expandat){

        for(auto i:vf){
            if(!expandat[i.second]){

                expandat[i.second] = 1;
                ne_expandat --;
                for(int vecin = 1; vecin<=n; vecin++){

                    if(cost[i.second] + gr[i.second][vecin] < cost[vecin]){
                        cost[vecin] = cost[i.second] + gr[i.second][vecin];

                        vf.insert({cost[vecin],vecin});
                    }
                }

                break;

            }
        }

    }

    for(int i = 2; i<=n; ++i)
        fout<<cost[i]<<" ";

    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;
    }

}