#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#define INF 1000000001
#define NMAX 100001

using namespace std;

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

struct varf{
    int x, c;
    friend bool operator >(varf, varf);
};

bool operator >(varf a, varf b)
{
    return a.c > b.c;
}

vector<varf> G[NMAX];
int n, m, start;
bool uz[NMAX];
int cmin[NMAX];
int prec[NMAX];

priority_queue<varf, vector<varf>, greater<varf> > H;

void citire()
{
    varf aux;
    int a;
    fin >> n >> m;
    start = 1;
    for(int i = 1; i <= n; i++)
    {
        cmin[i] = INF;
        prec[i] = start;
    }
    cmin[start] = 0, prec[start] = 0;

    for(int i = 1; i <= m; ++i)
    {
        fin >> a >> aux.x >> aux.c;
        G[a].push_back(aux);
    }
    uz[start] = 1;
    for(int i = 0; i < G[start].size(); i++)
    {
        H.push(G[start][i]);
        cmin[G[start][i].x] = G[start][i].c;
        prec[G[start][i].x] = start;
    }
}

void dijkstra()
{
    varf aux, dalta;
    int nr = 1;
    while(nr < n && !H.empty())
    {
        aux = H.top();
        H.pop();
        if(!uz[aux.x])
        {
            uz[aux.x] = 1;
            for(int i = 0; i < G[aux.x].size(); i++)
            {
                if(cmin[aux.x] + G[aux.x][i].c < cmin[G[aux.x][i].x] && !uz[G[aux.x][i].x])
                {
                    cmin[G[aux.x][i].x] = cmin[aux.x] + G[aux.x][i].c;
                    prec[G[aux.x][i].x] = aux.x;
                    dalta.x = G[aux.x][i].x;
                    dalta.c = G[aux.x][i].c;
                    H.push(dalta);
                }
            }
            nr++;
        }
    }
}

void afisare()
{
    for(int i = 2; i <= n; i++)
        if(cmin[i] != INF) fout << cmin[i] << ' ';
        else fout << -1 << ' ';
}

int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}