#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#define DN 50001
#define cst first
#define nod second
#define inf 1<<30
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m, cost[DN], viz[DN];
vector< pair < int, int> > v[DN];
priority_queue < pair < int, int > , vector < pair < int, int > > , greater < pair < int, int > > > pq;

void Dijkstra()
{
    pair < int, int > first;
    cost[1]=0;
    pq.push(make_pair(cost[1],1));
    while(!pq.empty())
    {
        first=pq.top();
        int vec=first.nod;
        pq.pop();
        if(viz[vec]==1)
            continue;
        viz[vec]=1;
        for(int i=0; i<v[vec].size(); i++)
            if(cost[v[vec][i].nod]>cost[vec]+v[vec][i].cst)
            {
                pq.push(make_pair(cost[vec]+v[vec][i].cst, v[vec][i].nod));
                cost[v[vec][i].nod]=cost[vec]+v[vec][i].cst;
            }
    }
}

int main()
{
    f>>n>>m;
    for(int i=1; i<=n; i++)
        cost[i]=inf;
    for(int i=0; i<m; i++)
    {
        int a,b,c;
        f>>a>>b>>c;
        v[a].push_back(make_pair(c,b));
    }
    Dijkstra();
    for(int i=2; i<=n; i++)
        if(cost[i]!=inf)
            g<<cost[i]<<" ";
        else g<<0<<" ";
    return 0;
}