#include <bits/stdc++.h>
using namespace std;
const int MAX_V = 50005;
const int INF = 1000000000;
struct Edge
{
    int neighbour;
    int weight;
};
int V,p,a,b,c,m;
vector<Edge> neighbours[MAX_V];
bool solved[MAX_V];
int DijkstraParent[MAX_V];
int minDist[MAX_V];
struct Vertex
{
    int minDist;
    int vertex;
};
bool operator < (const Vertex &first, const Vertex &second)
{
    return first.minDist > second.minDist;
}
void dijkstra(int source)
{
    for (int u = 0; u <= V; u++)
    {
        minDist[u] = INF;
    }
    priority_queue<Vertex> pq;
    DijkstraParent[source] = -1;
    minDist[source] = 0;
    pq.push(Vertex{minDist[source], source});
    int a=0;
    while (!pq.empty())
    {
        a++;
        Vertex vertex = pq.top();
        pq.pop();
        if (vertex.minDist>minDist[vertex.vertex])
            continue;
        int u = vertex.vertex;
        solved[u] = true;
        for (Edge e : neighbours[u])
        {
            int v = e.neighbour;
            //cout<<v;
            if (minDist[u] + e.weight < minDist[v])
            {
                DijkstraParent[v] = u;
                minDist[v] = minDist[u] + e.weight;
                pq.push(Vertex{minDist[v], v});
            }
        }
    }
}
int main()
{
    ifstream f ("dijkstra.in");
    ofstream g ("dijkstra.out");
    f>>V>>m;
    for (int i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        neighbours[a].push_back(Edge{b,c});
    }
    dijkstra(1);
    for (int i=2; i<=V; i++)
    {
        if (minDist[i]==INF)
            g<<0<<' ';
        else
            g<<minDist[i]<<' ';
    }
}