///Andrei Muntean 2017

#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;
priority_queue<pair<int,int> , vector<pair<int,int> >, greater<pair<int,int> > > vf;
vector<pair<int,int> > gr[N_MAX];
bool inq[N_MAX];

void citire();

int main()
{
    citire();

    vf.push({0,1});
    inq[vf.top().second] = true;
    cost[1] = 0;
    ne_expandat = n;
    bool am_de_exp = 1;

    while(!vf.empty()){

        am_de_exp = false;

        pair<int,int> i = vf.top();
        inq[vf.top().second] = false;
        vf.pop();

            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]){
                        cost[vecin.first] = i.first + vecin.second;
                        if(!inq[vecin.first]){
                            vf.push({cost[vecin.first],vecin.first});
                            inq[vf.top().second] = true;
                        } else cout<<"j";
                        gasit = true;
                    }
                }

            }

    }

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

}