#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define MAXN 50001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,x,y,travelcost[MAXN],z,viz[MAXN];
vector <vector <int>> v(MAXN),cost(MAXN);
auto cmp=[](pair <int,int> a,pair <int,int> b)
{
    if (a.first>b.first)
        return 1;
    else if (a.first==b.first)
    {
        if (a.second>b.second)
            return 1;
        return 0;
    }
    return 0;
};
priority_queue <pair <int,int>,std :: vector <pair<int,int>>,decltype(cmp)> q(cmp);
void dijkstra (int start)
{
    q.push(make_pair(0,start));
    while (!q.empty())
    {
        pair <int,int> a=q.top();
        viz[a.second]=0;
        //cout<<a.first<<'\n';
        q.pop();
        for (int j=0; j<v[a.second].size(); j++)
        {
            int next=v[a.second][j];
            if (travelcost[next]==0 || travelcost[next]>travelcost[a.second]+cost[a.second][j])
            {
                travelcost[next]=travelcost[a.second]+cost[a.second][j];
                if (viz[next]==0)
                {
                    viz[next]=1;
                    q.push(make_pair(travelcost[next],next));
                }
            }
        }
    }
}
int main()
{
    f>>n>>m;
    for (int i=1; i<=m; i++)
    {
        f>>x>>y>>z;
        v[x].push_back(y);
        cost[x].push_back(z);
    }
    dijkstra(1);
    for (int i=2; i<=n; i++)
    {
        g<<travelcost[i]<<' ';
    }
    return 0;
}