#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

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

const int NMAX = 1000;

struct MUCHIE
{
    int nod, cost;
};

bool operator<(const MUCHIE& a, const MUCHIE& b)
{
    if (a.cost == b.cost)
    {
        return a.nod > b.nod;
    }
    return a.cost > b.cost;
}

std::vector <MUCHIE>G[NMAX + 5];
int n, viz[NMAX + 5], cost[NMAX + 5];

void Dijkstra(int start)
{
    memset(cost, 0b01111111, sizeof(cost));
    MUCHIE m;
    std::priority_queue <MUCHIE> pq;
    pq.push({start, 0});
    while (!pq.empty())
    {
        while (!pq.empty() && viz[pq.top().nod])
        {
            pq.pop();
        }
        if (pq.empty())
        {
            break;
        }
        m = pq.top();
        pq.pop();
        viz[m.nod] = 1;
        for (auto it : G[m.nod])
        {
            if (!viz[it.nod] && cost[it.nod] > m.cost + it.cost)
            {
                cost[it.nod] = m.cost + it.cost;
                pq.push({it.nod, cost[it.nod]});
            }
        }
    }
}

int main()
{
    int m, x, y, z;
    fin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        fin >> x >> y >> z;
        G[x].push_back({y, z});
    }
    Dijkstra(1);
    for (int i = 2; i <= n; ++i)
    {
        fout << cost[i] << ' ';
    }
    return 0;
}