#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define nmax 100001
using namespace std;

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

vector <int> v[nmax];
queue <int> q;
int n,m,s,a,b,i,c,nod[nmax],p[5000][5000];

void bfs()
{

    while (!q.empty())
    {
        int cur=q.front();

        q.pop();

        for (i=0; i<v[cur].size(); i++)
            if (nod[v[cur][i]]<=0)
            {
                nod[v[cur][i]]=nod[cur]+p[cur][v[cur][i]];
                q.push(v[cur][i]);
            }
    }

}

int main()
{

    f>>n>>m;
    q.push(1);

    for (i=1; i<=n; i++)
        nod[i]=0;
    nod[1]=0;
    for (i=1; i<=m; i++)
    {
        f>>a>>b>>c;
        v[a].push_back(b);
        p[a][b]=c;
    }

    bfs();
    for (i=2; i<=n; i++)
        g<<nod[i]<<" ";

    return 0;
}