#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int NMAX=50005,INF=1000000009;
int cost[NMAX];
bool bo[NMAX];
int n,m;
int a,b,c;
struct edg
{
    int nod,cost;
};
vector<edg> adj[NMAX];
priority_queue<edg> pq;
inline bool operator <(edg a,edg b)
{
    return a.cost>b.cost;
}
edg aux;
void dijk()
{
    while(!pq.empty())
    {
        edg el=pq.top();
        pq.pop();
        if(bo[el.nod]==0)
        {
            bo[el.nod]=1;
            cost[el.nod]=el.cost;
            for(auto w:adj[el.nod])
            {
                aux.nod=w.nod;
                aux.cost=el.cost+w.cost;
                pq.push(aux);
            }
        }
    }
}
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>a>>b>>c;
        aux.nod=b;
        aux.cost=c;
        adj[a].push_back(aux);
    }
    aux.nod=1;
    aux.cost=0;
    pq.push(aux);
    dijk();
    for(int i=2;i<=n;i++)
    {
        out<<cost[i]<<" ";
    }
}