#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

struct memo
{
    int ter;
    int val;
}x;
struct use
{
    bool ver;
    int dis;
    vector <memo> v;
}d[50001];

queue <int> q;
int n, m;
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a1;
        fin>>a1>>x.ter>>x.val;
        d[a1].v.push_back(x);
        d[a1].ver=false;
        d[a1].dis=INT_MAX;
        d[x.ter].dis=INT_MAX;
    }
    q.push(1);
    d[1].dis=0;
    while(!q.empty())
    {
        int nod=q.front();
        q.pop();
        d[nod].ver=true;
        for(int i=0;i<d[nod].v.size();i++)
        {
            if(d[nod].v[i].val+d[nod].dis<d[d[nod].v[i].ter].dis && d[d[nod].v[i].ter].ver==false)
            {
                d[d[nod].v[i].ter].dis=d[nod].v[i].val+d[nod].dis;
                q.push(d[nod].v[i].ter);
            }
        }
    }
    for(int i=2;i<=n;i++)
    {
        fout<<d[i].dis<<' ';
    }
    return 0;
}