#include <iostream>
#include <fstream>
#include <map>
#include <string.h>
#include <string>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

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

int n,m;
struct ed
{
    int x,y,w;
};
vector<ed> E[50000];
struct pp
{
    int x, w;
};

int ww[50000];

bool comp(pp x, pp y)
{
if (x.w==y.w) return (x.x<y.x);
else return (x.w<y.w);
}

void Dijkstra()
{
    memset(ww,-1,sizeof(ww));
    ww[0]=0;
    multiset<pp,bool (*) (pp,pp)> q(comp);
    {pp t; t.x=0; t.w=0; q.insert(t);}

    while(q.size())
    {
        pp t;
        t = *(q.begin());
        q.erase(q.begin());

        for (int i=0; i<E[t.x].size(); i++)
        {
            if (ww[E[t.x][i].y]==-1)
            {
                ww[E[t.x][i].y]= ww[t.x] + E[t.x][i].w;
                pp tt;
                tt.x=E[t.x][i].y;
                tt.w=ww[E[t.x][i].y];
                q.insert(tt);
                continue;
            }

            if (ww[E[t.x][i].y]> ww[t.x] + E[t.x][i].w)
            {
                pp tt;
                tt.x=E[t.x][i].y;
                tt.w=ww[E[t.x][i].y];
                q.erase(q.find(tt));
                ww[t.x]=ww[t.x] + E[t.x][i].w;
                tt.w = ww[tt.x];
                q.insert(tt);
            }
        }
    }
}

int main()
{
    fin>>n>>m;
    for (int i=0; i<m; i++)
    {
        int x,y,w;
        fin>>x>>y>>w;
        x--;
        y--;
        ed t;
        t.x=x;
        t.y=y;
        t.w=w;
        E[x].push_back(t);
    }

    Dijkstra();

    for (int i=1; i<n; i++)
        fout<<ww[i]<<' ';

    return 0;
}