#include <fstream>
#include <vector>
#include <set>
#define nmax 250005

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct noduri
{
    int vecini, distanta;
};

struct cmp
{
    bool operator() (const noduri& a, const noduri& b) const
    {return a.distanta <b.distanta;}
};

vector <noduri> graf[nmax];
multiset <noduri, cmp> q;
int vdist[nmax];

void dijkstra(int x)
{
    noduri p;
    noduri aux;
    //vdist[1] = 0;
    p.distanta = 0;
    p.vecini = x;
    q.insert(p);
    while(!q.empty())
    {
        aux = *q.begin();
        if(vdist[aux.vecini]!=-1)
        {
            q.erase(q.begin());
            continue;
        }
        vdist[aux.vecini] = aux.distanta;
        for(int i=0; i<graf[aux.vecini].size(); i++)
        {
            p.distanta = graf[aux.vecini][i].distanta  + aux.distanta;
            p.vecini = graf[aux.vecini][i].vecini;
            q.insert(p);
        }
        q.erase(q.begin());
    }
}

int a, b, n, m, val;

int main()
{
    noduri o;
    in>>n>>m;
    for(int i=1; i<=n; i++)
          vdist[i]=-1;
    for(int i=1; i<=m; i++)
    {
        in>>a>>b>>val;
        o.vecini = b;
        o.distanta = val;
        graf[a].push_back(o);
    }
    dijkstra(1);
    for(int i=2; i<=n; i++)
    {
        out<<vdist[i]<<" ";
    }
    return 0;
}