#include <fstream>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>

#define to first
#define weight second

using namespace std;

vector< vector<pair<int,int> > >graf;
vector<int> dist,is_visited;
set<pair<int,int> >q;
set<pair<int,int> >::iterator it;
int n,m,oo=1<<30;

void dijkstra(int start_node)
{
    int current_node,i;
    for(i=1;i<=n;i++)
        q.insert(make_pair(dist[i],i));
    while(!q.empty())
    {
        current_node=(*q.begin()).second;
        q.erase(*q.begin());
        for(i=0;i<graf[current_node].size();i++)
        {
                if(dist[graf[current_node][i].first]>dist[current_node]+graf[current_node][i].second)
                {
                    dist[graf[current_node][i].first] = dist[current_node]+graf[current_node][i].second;
                    q.insert(make_pair(dist[graf[current_node][i].first],graf[current_node][i].first));
                }
        }
    }
}

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int i,u,v,w;
    f>>n>>m;
    graf.resize(n+1);
    is_visited.resize(n+1);
    is_visited[1]=1;
    for(i=0;i<=n;i++)
        dist.push_back(oo);
    dist[1]=0;
    for(i=1;i<=m;i++)
    {
        f>>u>>v>>w;
        graf[u].push_back(make_pair(v,w));
    }
    dijkstra(1);
    for(i=2;i<=n;i++)
        g<<dist[i]<<' ';
    return 0;
}