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


using namespace std;


const int INF = 9999999;
const int MAXN = 5000;
struct Edge { int to, cost;};
struct Edges {Edge edges[MAXN];int k = 0;};

Edges ADJ[MAXN];
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 (int i = 0; i< ADJ[x].k ; i++)
        {

            int node = ADJ[x].edges[i].to;
            int cost = ADJ[x].edges[i].cost;


            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;
        int k = ADJ[x].k;
        ADJ[x].edges[k].to = y;
        ADJ[x].edges[k].cost = c;
        ADJ[x].k++;

    }

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


    return 0;
}