#include <fstream>
#include <vector>
#include <set>

using namespace std;

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

const int INF = 0x3f3f3f3f;

vector<pair<int, int > > Muchii[50005];
int cost[50005], n, m;
bool unvizited[50005];
int cnt = 1;
set<pair<int, int> > tc;

void GetTheCost(){
    int nod = 1;
    while(cnt < n){
        for(int i = 0; i < Muchii[nod].size(); ++i)
            if(unvizited[Muchii[nod][i].first] == 1){
                int c = cost[nod] + Muchii[nod][i].second;
                if(c < cost[Muchii[nod][i].first]){
                    cost[Muchii[nod][i].first] = c;
                    tc.insert({c, Muchii[nod][i].first});
                }
            }
        unvizited[nod] = 0;
        ++cnt;
        while(!tc.empty() && unvizited[tc.begin()->second] == 0)
            tc.erase(tc.begin());
        nod = tc.begin()->second;
        tc.erase(tc.begin());
    }
}

int main()
{
    fin >> n >> m;

    for(int i = 1; i <= n; ++i)
        cost[i] = INF, unvizited[i] = 1;
    for(int i = 1; i <= m; ++i){
        int x, y, c;
        fin >> x >> y >> c;

        Muchii[x].push_back({y, c});
    }

    cost[1] = 0;
    GetTheCost();

    for(int i = 2; i <= n; ++i)
        fout << cost[i] << ' ';
    fout << '\n';
    return 0;
}