#include <bits/stdc++.h>
#define NMAX 50500
using namespace std;
struct poz{
    int val, no;

    bool operator < (poz b) const{
        return val>b.val;
    }
};
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
long long d[NMAX];
priority_queue<poz> q;
set<pair<long long,int>> v[NMAX];
int n,m,x,a,c;
int main()
{
    fin>>n>>m;

    for(int i=1;i<=m;++i)
    {
        fin>>x>>a>>c;
        v[x].insert({a,c});
    }

    d[1]=0;
    for(int i=2;i<=n;++i)
        d[i]=2e12;

    for(int i=1;i<=n;++i)
        q.push({d[i],i});

    while(q.empty()==false)
    {
        x=q.top().no;
        q.pop();

        for(auto y:v[x])
            if(d[y.first]>d[x]+y.second)
        {
            d[y.first]=d[x]+y.second;
            q.push({d[y.first],y.first});
        }
    }

    for(int i=2;i<=n;++i)
        fout<<d[i]<<" ";

    return 0;
}