#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define s second
#define f first
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector <pair<int,int> > v[50010];
priority_queue <pair <int,int> ,vector<pair<int,int> > ,greater< pair<int,int > > > q;
pair <int,int> p;
int N,M,viz[50010],ans[50010];
int main()
{
    int x1,x2,c,i;
    fin>>N>>M;
    for(i=1;i<=M;i++)
    {
        fin>>x1>>x2>>c;
        v[x1].push_back(make_pair(c,x2));
    }
    for(auto it:v[1])
    {
        q.push(it);
    }
    viz[1]=1;
    while(!q.empty())
    {
        p=q.top();
        q.pop();
        if(viz[p.s]==0)
        {
            ans[p.s]=p.f;
            for(auto it:v[p.s])
            {
                if(viz[it.s]==0)
                q.push(make_pair(ans[p.s]+it.f,it.s));
            }
            viz[p.s]=1;
        }
    }
    for(i=2;i<=N;i++)
    {
        fout<<ans[i]<<' ';
    }
}