#include <fstream>
#include <set>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
queue <pair <int, int> >nod[50005];
set <pair <int, int> > catre;
const int INF=999999;
int n,m,a,b,c,sursa=1,dist[50005],nextpoz,aux;
void Create_graph(int s)
{
    for(int i=1;i<=n;i++)
    {
        if(i!=sursa) {catre.insert(make_pair(INF,i));dist[i]=INF;}
    }
    catre.insert(make_pair(0,sursa));
    dist[sursa]=0;
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        nod[a].push(make_pair(c,b));

    }
    Create_graph(sursa);
    while(!catre.empty())
    {
        int cost=catre.begin()->first;
        int poz=catre.begin()->second;
        while(!nod[poz].empty())
        {
            if(dist[nod[poz].front().second]> dist[poz]+nod[poz].front().first)
            {
                catre.erase(catre.find(make_pair(dist[nod[poz].front().second],nod[poz].front().second)));
                dist[nod[poz].front().second]= dist[poz]+nod[poz].front().first;
                catre.insert(make_pair(dist[nod[poz].front().second],nod[poz].front().second));
            }
            nod[poz].pop();
        }
         catre.erase(catre.find(make_pair(cost,poz)));
    }
    for(int i=2;i<=n;i++)
        fout<<dist[i]<<' ';
    return 0;
}