#include<iostream>
#include<list>
#include<set>
#include <vector>
#include<fstream>
using namespace std;
# define INF 0x3f3f3f3f
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
class Graph
{
    int V,M;
    list< 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;
   // adj = new list< pair<int, int> >[g];
    int i;
    for(i=1;i<=M;i++)
    {
        f>>v1>>v2>>dis;
        adj[v1].push_back(make_pair(v2,dis));
        adj[v2].push_back(make_pair(v1,dis));
    }
    
}
Graph::Graph()
{
    f>>V;
    V++;
    adj = new list< pair<int, int> >[V];
}

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)
{
    int parent[V+1];
        parent[1] = -1;
   
    set< pair<int, int> > setds;

    vector<int> dist(V, INF);
    

    setds.insert(make_pair(0, src));
    dist[src] = 0;
    while (!setds.empty())
    {
       
        pair<int, int> tmp = *(setds.begin());
        setds.erase(setds.begin());
     
        int u = tmp.second;
        
        list< pair<int, int> >::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
        {
         
            int v = (*i).first;
            int weight = (*i).second;
            
            if (dist[v] > dist[u] + weight)
            {
                if (dist[v] != INF)
                    setds.erase(setds.find(make_pair(dist[v], v)));
                
                dist[v] = dist[u] + weight;
                parent[v]=u;
                setds.insert(make_pair(dist[v], v));
            }
        }
    }
    for (int i = 2; i < V; ++i)
        //printf("%d ",dist[i]);
       g<<dist[i]<<" ";

    
}

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