#include <bits/stdc++.h>

struct edge
{
    int v, cost;
};

int nodes, edges, u, v, cost;

std :: vector<edge> adj[50001];

int distance[50001], OO = 20001;

struct orderByDistance
{
    bool operator()(int a, int b)
    {
        return distance[a] > distance[b];
    }
};

std :: priority_queue<int, std :: vector<int>, orderByDistance> q;

void Dijkstra(int start)
{
    for(int i = 1; i <= nodes; i++)
    {
        distance[i] = i == start ? 0 : OO;

        q.push(i);
    }

    while(!q.empty())
    {
        int u = q.top(); q.pop();

        for(edge i : adj[u])
        {
            int v = i.v, cost = i.cost;

            if(distance[v] > distance[u] + cost)
            {
                distance[v] = distance[u] + cost;
            }
        }
    }
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    scanf("%d %d", &nodes, &edges);

    for(int i = 1; i <= edges; i++)
    {
        scanf("%d %d %d", &u, &v, &cost);

        adj[u].push_back({v, cost});
    }

    Dijkstra(1);

    for(int i = 2; i <= nodes; i++)
    {
        printf("%d ", distance[i] == OO ? 0 : distance[i]);
    }

    return 0;
}

///function Dijkstra(Graph, source):

///      create vertex set Q

///      for each vertex v in Graph:             // Initialization
///          dist[v] ← INFINITY                  // Unknown distance from source to v
///          prev[v] ← UNDEFINED                 // Previous node in optimal path from source
///          add v to Q                          // All nodes initially in Q (unvisited nodes)

///      dist[source] ← 0                        // Distance from source to source

///      while Q is not empty:
///          u ← vertex in Q with min dist[u]    // Node with the least distance will be selected first
///          remove u from Q

///          for each neighbor v of u:           // where v is still in Q.
///              alt ← dist[u] + length(u, v)
///              if alt < dist[v]:               // A shorter path to v has been found
///                  dist[v] ← alt
///                  prev[v] ← u

///      return dist[], prev[]