#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int maxn = 50005;
const int inf = (1 << 30);
vector <pair <int, int> > v[maxn];
int dist[maxn];
pair <int, int> H[maxn];
int pozitii[maxn];
int last = 0;
int lg = 0;
void up(int F)
{
    if(F / 2 >= 1 && H[F].first < H[F / 2].first)
    {
        swap(pozitii[H[F / 2].second], pozitii[H[F].second]);
        swap(H[F], H[F / 2]);
        //pozitii[H[F].second] = F;
        //pozitii[H[F / 2].second] = F / 2;
        up(F / 2);
    }
    return;
}

void down(int F)
{
    int S = F * 2;
    if(S < lg && H[S].first > H[S + 1].first)
        S++;
    if(S <= lg && H[S].first < H[F].first)
    {
        swap(pozitii[H[F].second], pozitii[H[S].second]);
        swap(H[S], H[F]);
        //pozitii[H[F].second] = F;
        //pozitii[H[S].second] = S;
        down(S);
    }
}

void _erase_(int pos)
{
    swap(pozitii[H[pos].second], pozitii[H[lg].second]);
    swap(H[pos], H[lg]);
    lg--;
    up(pos);
    down(pos);
}

void inserare(int x)
{
    lg++;
    last++;
    H[lg] = make_pair(x, last);
    pozitii[last] = lg;
    up(lg);
    return;
}
void dijkstra()
{
    while(lg > 0)
    {
        pair <int, int> elmn = H[1];
        _erase_(1);
        for(auto it : v[elmn.second])
        {
            int p = it.second;
            if(dist[it.first] > dist[elmn.second] + p)
            {
                dist[it.first] = dist[elmn.second] + p;
                int pos = pozitii[it.first];
                H[pos].first = dist[it.first];
                up(pos);
                down(pos);
            }
        }
    }
}


int main()
{
    int n, m;
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, cost;
        in >> x >> y >> cost;
        v[x].push_back(make_pair(y, cost));
    }
    for(int i = 2; i <= n; i++)
        dist[i] = inf;
    inserare(0);
    for(int i = 2; i <= n; i++)
        inserare(inf);
    dijkstra();
    for(int i = 2; i <= n; i++)
    {
        if(dist[i] == inf)
            out << 0 << " ";
        else
            out << dist[i] << " ";
    }
    return 0;
}