#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <set>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 50000;


vector<pair<int, int>> ADJ[MAXN];
int dist[MAXN];

void dijkstra()
{

    set<pair<int, int>> Q;
    Q.insert(make_pair(0, 1));

    while (!Q.empty())
    {
        int x = Q.begin()->second;
        Q.erase(Q.begin());


    for (auto edge : ADJ[x])
        {
            int node = edge.first;
            int cost = edge.second;

            if (dist[x] + cost < dist[node])
            {
                if(dist[node]!= INF)
                   Q.erase(Q.find(make_pair(dist[node], node)));
                dist[node] = dist[x] + cost;
                Q.insert(make_pair(dist[node], node));
            }
        }
    }

}

int main()
{
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");

    int N,M;
    in>>N>>M;

    for (int i = 0; i < M; i++)
    {
        int x, y, c;
        in>>x>>y>>c;
        ADJ[x].push_back(make_pair(y,c));

    }
    memset(dist, INF, sizeof dist);
    dist[1] = 0;

    dijkstra();
    for (int i = 2; i <= N; i++)
    {
        if (dist[i] == INF)
        {
            dist[i] = 0;
        }
        out << dist[i] << ' ';
    }
    out << '\n';


    return 0;
}