#include <fstream>
#include <set>
#include <vector>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector <pair <int, int> >nod[50005];
set <pair <int, int> > catre;
const int INF=999999;
int n,m,a,b,c,sursa=1,dist[50005];
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_back(make_pair(c,b));

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