#define fisier "dijkstra"
#include <fstream>
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");
const long long N = 50000, C = 20000, INF = N*C;
long long dist[N];
#include <utility>
using Arc = std::pair<int, int>;
#include <vector>
std::vector<Arc> deLa[N];
#include <queue>
int main()
{
    int n, m;
    in >> n >> m;
    while (m--)
    {
        int a, b, c;
        in >> a >> b >> c;
        deLa[--a].push_back({c, --b});
    }
    for (int i = 1; i < n; i++)
        dist[i] = INF;
    std::priority_queue<Arc, std::vector<Arc>, std::greater<Arc>> pq;
    for (pq.push({C, 0}); pq.size();)
    {
        const int front = pq.top().second, d = pq.top().first; pq.pop();
        if (d == dist[front]) // Optimizare
            for (auto arc: deLa[front])
                if (dist[front] + arc.first < dist[arc.second])
                {
                    dist[arc.second] = dist[front] + arc.first;
                    pq.push({dist[arc.second], arc.second});
                }
    }
    for (int i = 1; i < n; i++)
        out << (dist[i] == INF? 0: dist[i]) << ' ';
}