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


using namespace std;


const int INF = 9999999;
const int MAXN = 50000;
vector<vector<pair<int, int>>> ADJ (MAXN+1);
int dist[MAXN];

void dijkstra()
{

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

    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])
            {
                Q.erase(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));

    }

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


    return 0;
}