#include <fstream>
#include <vector>
#include <set>
#define INF 5000001
using namespace std;
ifstream fi ("dijkstra.in");
ofstream fo ("dijkstra.out");
vector<pair<int,int>> v[250006];
int dist[250007],viz[250006],nrnod,nrmuchii;
set<pair<int,int>> myset;
int main()
{
    fi>>nrnod>>nrmuchii;
    for (int i=1;i<=nrmuchii;i++)
    {
        int x,y,z;
        fi>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
    }
    for (int i=1;i<=nrnod;i++) dist[i]=INF;
    myset.insert(make_pair(0,1));
    while (!myset.empty())
    {
        int dcur=myset.begin()->first;
        int nod=myset.begin()->second;
        myset.erase(myset.begin());
        for (int i=0;i<v[nod].size();i++)
        {
            int nodurm=v[nod][i].first;
            if (viz[nodurm]) continue;
            int d=v[nod][i].second;
            if (dcur+d<=dist[nodurm])
            {
                if (dist[nodurm]!=INF) myset.erase(myset.find(make_pair(dist[nodurm],nodurm)));
                dist[nodurm]=dcur+d;
                myset.insert(make_pair(dist[nodurm],nodurm));
            }
        }
        viz[nod]=1;
    }
    for (int i=2;i<=nrnod;i++) fo<<dist[i]*(dist[i]!=INF)<<' ';
    return 0;
}