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

ifstream fin("djikstra.in");
ofstream fout("djikstra.out");
const int NMAX = 50002;
vector < pair <int, int> > v[NMAX];
multimap <int, pair <int, int> > q;
int dist[NMAX], N, M;
bool vis[NMAX];
int main()
{
    fill_n(dist, NMAX, 1e9);
    dist[1] = 0;
    fin>>N>>M;
    int a, b, c;
    for(int i = 1; i <= M; i++)
    {
        fin>>a>>b>>c;
        v[a].push_back(pair<int, int>(b, c));
    }
    int p = 1, y;
    pair <int, int> x;
    for(auto i : v[1]) {
        pair <int, int> _;
        _.first = 1;
        _.second = i.first;
        q.insert(pair<int, pair <int, int> >(i.second, _));
        }
    vis[1] = 1;
    while(!q.empty())
    {
        x = q.begin() -> second;
        y = q.begin() -> first;
        q.erase(q.begin());
        dist[x.second] = min(dist[x.second], dist[x.first] + y);
        if(!vis[x.second])
        {

            for(auto i : v[x.second])
            {
                pair <int, int> _;
                _.first = x.second;
                _.second = i.first;
                q.insert(pair<int, pair <int, int> >(i.second, _));
            }
            vis[x.second] = 1;
        }

    }
    for(int i = 2; i <= N; i++)
        fout<<dist[i]<<" ";
    return 0;
}