#include <bits/stdc++.h>
using namespace std;
ifstream f ( "dijkstra.in" );
ofstream g ( "dijkstra.out" );
vector < pair <int,int> > v[50004];
set <pair <int,int> >  s;
int rasp[50004];
bool vizitat[50004];
void parcurgere(int nod)
{   vizitat[nod]=1;
    for(int i=0;i<v[nod].size();i++)
    {   int vecin=v[nod][i].second;
        int cost=v[nod][i].first;
        if(!vizitat[vecin])
        {   vizitat[vecin]=1;
            rasp[vecin]=rasp[nod]+cost;
            s.insert({rasp[vecin],vecin});
        }
        else
        {   if(rasp[nod]+cost<rasp[vecin])
            {   s.erase({rasp[vecin],vecin});
                rasp[vecin]=rasp[nod]+cost;
                s.insert({rasp[vecin],vecin});
            }
        }
    }
}
int main()
{   int n,m;
    f>>n>>m;
    for(int i=1,a,b,c;i<=m;i++)
    {   f>>a>>b>>c;
        v[a].push_back({c,b});
    }
    rasp[1]=0;
    s.insert({0,1});
    while(!s.empty())
    {   int nod=(*s.begin()).second;
        s.erase(s.begin());
        parcurgere(nod);
    }
    for(int i=2;i<=n;i++)
        g<<rasp[i]<< ' ';
    return 0;
}