#include<iostream>
#include<list>
#include<set>
#include <vector>
#include<fstream>
using namespace std;
# define INF 0x3f3f3f3f
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int dist[50005];
class Graph
{
    int V,M;
    vector< pair<int, int> > *adj;
    
public:
    Graph();
    void addEdge(int u, int v, int w);
    void insert();
    void shortestPath(int s);
};
void Graph::insert()
{
    int h;
    f>>h;
    int v1,v2,dis;
    M=h;
    int i;
    for(i=1;i<=M;i++)
    {
        f>>v1>>v2>>dis;
        adj[v1].push_back(make_pair(v2,dis));
        dist[v1]=INF;
        dist[v2]=INF;
    }
    
}
Graph::Graph()
{
    f>>V;
    V++;
    adj = new vector< pair<int, int> >[V+1];
}

/*void Graph::addEdge(int u, int v, int w)
{
    adj[u].push_back(make_pair(v, w));
    adj[v].push_back(make_pair(u, w));
}*/
void printPath(int *parent, int j)
{
    if (parent[j]==-1)
        return;
    
    printPath(parent, parent[j]);
    
    printf("%d ", j);
}
void Graph::shortestPath(int src)
{
  set< pair<int, int> > setds;
    setds.insert(make_pair(0, 1));
    while (!setds.empty())
    {
       
        int u = setds.begin()->second;
        int best=setds.begin()->first;
        setds.erase(setds.begin());
        for (pair<int,int> i:adj[u])
        {
         
            int v = i.first;
            int weight = i.second;
            
            if (dist[v] > best + weight)
            {
                if (dist[v] != INF)
                    setds.erase(make_pair(dist[v], v));
                
                dist[v] = best + weight;

                setds.insert(make_pair(dist[v], v));
            }
        }
    }
    for (int i = 2; i < V; ++i)
       if(dist[i]!=INF)
       g<<dist[i]<<" ";
    else g<<0<<" ";

    
}

int main()
{
    Graph g;
    g.insert();
    g.shortestPath(1);
    
    return 0;
}