#include <bits/stdc++.h>
#define mp make_pair
#define f first
#define s second
#define nmax 55000
#define pb push_back
#define inf 1e9
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

typedef pair<int,int> p;

vector <p> v[nmax+1];

priority_queue <p,vector<p>,greater<p> > h;

int ans[nmax+1],w[nmax+1];
int n,m,i,a,b,c,nod;

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        v[a].pb(mp(c,b));
    }
    ans[1]=0;
    fill(ans+2,ans+n+2,inf);
    h.push(mp(0,1));
    while(h.size())
    {
        nod=h.top().s;
        h.pop();
        w[nod]=1;
        for(i=0;i<v[nod].size();i++)
        {
            if(!w[v[nod][i].s] && ans[nod]+v[nod][i].f<ans[v[nod][i].s])
            {
                ans[v[nod][i].s]=ans[nod]+v[nod][i].f;
                h.push(mp(ans[v[nod][i].s],v[nod][i].s));
            }
        }
    }
    for(i=2;i<=n;i++)
        fout<<ans[i]<<" ";
    return 0;
}