#include <iostream>
#include <fstream>
#include <vector>
#define INF 1000000000
#include <queue>

using namespace std;
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");

struct muchie{
    int nod, cost;
};
vector <muchie> v[50001];
priority_queue < pair<int,int> , vector<pair<int,int>> , greater<pair<int,int>> > pq;

int d[100000],s[100000];
int main()
{
    int n,m;
    in>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int x,y,z;
        in>>x>>y>>z;
        v[x].push_back({y,z});
    }
    for(int i=1;i<=n;i++) d[i]=INF;
    d[1]=0;
    pq.push({1,0});

    while(!pq.empty())
    {
        int nod = pq.top().first;
        pq.pop();
        if(s[nod]==0)
        {
            s[nod]=1;
            int l=v[nod].size();
            for(int i=0;i<l;i++)
            {
                if(v[nod][i].cost+d[nod]<d[v[nod][i].nod])
                {
                    d[v[nod][i].nod] = v[nod][i].cost+d[nod];
                    pq.push({ v[nod][i].nod, d[v[nod][i].nod] });
                }
            }
        }
    }

    for(int i=2;i<=n;i++) out<<d[i]<<' ';
    return 0;
}