#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int N = 50005, M = 250005, inf = 0x3f3f3f3f;

int dist[N], n;
bool use[N];

struct Nod
{
    int x, cost;

    Nod()
    {

    }

    Nod(int _x, int _cost)
    {
        x = _x;
        cost = _cost;
    }

    inline bool operator< (const Nod& N) const
    {
        return cost > N.cost;
    }
};

vector<Nod> graph[N];

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

void dijkstra(int x)
{
    int y, upt;

    priority_queue< Nod, vector<Nod> > H;

    memset(dist, inf, sizeof(dist));
    memset(use, false, sizeof(use));

    dist[x] = 0;

    H.push(Nod(x, 0));

    while (!H.empty())
    {
        x = H.top().x; H.pop();

        if (use[x])
            continue;

        use[x] = true;

        for (vector<Nod> :: iterator it = graph[x].begin() ; it != graph[x].end() ; it++)
        {
            y = (*it).x;
            upt = dist[x] + (*it).cost;
            if (upt < dist[y])
            {
                dist[y] = upt;
                H.push(Nod(y, upt));
            }
        }
    }
}

int main()
{
    int m, x, y, c;

    in >> n >> m;

    while (m--)
    {
        in >> x >> y >> c;
        graph[x].push_back(Nod(y, c));
    }

    dijkstra(1);

    for (int i = 2 ; i <= n ; i++)
        out << (dist[i] != inf ? dist[i] : 0) << " ";

    out << "\n";

    return 0;
}