#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define oo 1000000000
#define N 50010

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,x,y,c,d[N],z,i,a;
priority_queue<pair<int, int>,vector<pair<int,int> >, greater<pair<int, int> > > Q;
vector<pair<int, int> > v[N];
pair<int, int> P;

int main()
{
    f>>n>>m;
    for(; m; m--)
    {
        f>>x>>y>>z;
        v[x].pb(mp(y,z));
        //v[y].pb(mp(x,z));
    }
    for(i=2; i<=n; i++)
        d[i]=oo;
    Q.push(mp(0,1));
    while(Q.size())
    {
        P=Q.top();
        Q.pop();
        c=P.first;
        a=P.second;
        for(auto it:v[a])
        {
            if(d[it.first] > it.second + c)
            {
                d[it.first] = it.second + c;
                Q.push(mp(d[it.first],it.first));
            }
        }
    }
    for(i=2; i<=n; i++)
        g<<d[i]<<' ';
    g<<'\n';
    return 0;
}