/*#include<fstream>
#include<cstring>
#include<vector>
#include<set>
#define N 50001
#define INF 1000000001
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

int* Dijkstra(vector<pair<int, int> > *v, int n)
{
    int *dist = new int[n + 1];
    for(int i = 2; i <= n; ++i)
    {
        dist[i] = INF;
    }
    set<pair<int, int> > heap;
    
    heap.insert(make_pair(0, 1));
    
    while(!heap.empty())
    {
        int node = heap.begin() -> second;
        int bestDist = heap.begin() -> first;
        heap.erase(heap.begin());
        
        for(int i = 0; i < v[node].size(); ++i)
        {
            int to = v[node][i].first;
            int cost = v[node][i].second;
            if(dist[to] > bestDist + cost)
            {
                if(dist[to] != INF)
                {
                    heap.erase(make_pair(dist[to], to));
                }
                dist[to] = bestDist + cost;
                heap.insert(make_pair(dist[to], to));
            }
        }
    }
    
    return dist;
}

int main(){
    int n, m;
    cin >> n >> m;
    
    vector<pair<int, int> > v[1000];
    
    for(int i = 1; i <= m; ++i)
    {
        int from, to, cost;
        cin >> from >> to >> cost;
        v[from].push_back(make_pair(to, cost));
    }
    
    int *dist = Dijkstra(v, n);
    
    for(int i = 2; i <= n; ++i)
    {
        if(dist[i] == INF)
        {
            dist[i] = 0;
        }
        cout << dist[i] << " ";
    }
    
    cin.close();
    cout.close();
    return 0;
}*/


#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 = new int[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;
   // 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));
        dist[v1]=INF;
        dist[v2]=INF;
        //adj[v2].push_back(make_pair(v1,dis));
    }
    
}
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)
{
    //int parent[V+1];
     //   parent[1] = -1;
    //int *dist = new int[V + 1]();
   /* for(int i = 0; i <= V; ++i)
    {
        dist[i] = INF;
    }*/
   
    
    set< pair<int, int> > setds;
    setds.insert(make_pair(0, 1));
 //   dist[src] = 0;
    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;
                //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;
}