#include <fstream>
#include <vector>
#include <set>
#define NMAX 50001
#define inf 2000000000

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m, dist[NMAX];
vector < pair < int, int > > v[NMAX];
set < pair < int, int> > heap;

void read()
{
    f >> n >> m;

    int a, b, c;

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

void initialize()
{
    for (int i=2; i<=n; ++i)
        dist[i] = inf;
    dist[1] = 0;
}

void dijkstra()
{
    initialize();
    heap.insert(make_pair(1,0));

    while (heap.size())
    {
        int minim = heap.begin() -> first;
        heap.erase(heap.begin());

        for (int i=0; i<v[minim].size(); ++i)
            if (dist[v[minim][i].first] > dist[minim] + v[minim][i].second)
            {
                dist[v[minim][i].first] = dist[minim] + v[minim][i].second;
                heap.insert(make_pair(v[minim][i].first, dist[v[minim][i].first]));
            }
    }
}

int main()
{
    read();
    dijkstra();

    for (int i=2; i<=n; ++i)
        if (dist[i] == inf)
        g << "0 ";
    else
        g << dist[i] << " ";
    return 0;
}