#include <fstream>
#include <climits>
#include <vector>
#include <set>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define nmax 50001
#define pb push_back
#define mp make_pair
const int inf=INT_MAX;
vector <pair<int, int> > g[nmax];
int n, d[nmax];
void citire()
{
    int m, i, j, cost;
    fin>>n>>m;
    while(m)
    {
        m--;
        fin>>i>>j>>cost;
        g[i].pb(mp(j, cost));
    }
    fin.close();
}
void dijkstra(int nod)
{
    int k;
    vector <pair<int, int> > :: iterator it;
    multiset <pair<int, int> > heap;
    for(k=1; k<=n; k++)
        d[k]=inf;
    d[nod]=0;
    heap.insert(mp(d[nod], nod));
    while(!heap.empty())
    {
        k=heap.begin()->second;
        heap.erase(heap.begin());
        for(it=g[k].begin(); it!=g[k].end(); it++)
            if(d[it->first]>d[k]+it->second)
            {
                if(d[it->first]!=inf)
                    heap.erase(heap.find(mp(d[it->first], it->first)));
                d[it->first]=d[k]+it->second;
                heap.insert(mp(d[it->first], it->first));
            }
    }
}
void afisare()
{
    for(int i=2; i<=n; i++)
        fout<<d[i]<<' ';
    fout<<'\n';
    fout.close();
}
int main()
{
    citire();
    dijkstra(1);
    afisare();
    return 0;
}