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

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

const int N_MAX = 50000 + 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;
vector<pair<int,int> > gr[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(auto vecin : gr[i.second]){
                    if(i.first + vecin.second < cost[vecin.first]){
                        vf.erase({cost[vecin.first],vecin.first});
                        cost[vecin.first] = i.first + vecin.second;
                        vf.insert({cost[vecin.first],vecin.first});
                        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)
            cost[i] = INF;


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

}