#include <fstream>
#include <vector>
#include <set>

using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
int len,x,y,i,n,m;
struct nod
{
    int drum=-1;
    vector <pair <int, int>> vecini;
} v[50001];
set <pair <long long, int>> drum;
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>len;
        v[x].vecini.push_back(make_pair(y, len));
    }
    drum.insert(make_pair(0,1));
    while(!drum.empty())
    {
        auto it=drum.begin();
        if(v[it->second].drum>it->first || v[it->second].drum==-1)
        {
            v[it->second].drum=it->first;
            for(auto par : v[it->second].vecini)
                drum.insert(make_pair(it->first+par.second, par.first));
        }
        drum.erase(it);
    }
    for(i=2;i<=n;i++)
        fout<<v[i].drum<<' ';
    return 0;
}