#include<iostream>
#include<vector>
#include<fstream>
#include<queue>
#include<math.h>
using namespace std;

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

#define nmax 50005

int n,m,x,y,cost,d[nmax],i,nod;
vector <int> arc[nmax];
vector <int> costul[nmax];
queue <int> q;

void bfs()
{
    q.push(1);

    d[1]=0;
    while(q.empty()!=1)
    {
        nod=q.front();
        q.pop();
        for(int i=0;i<arc[nod].size();i++)
        {
            d[arc[nod][i]]=min(d[arc[nod][i]],d[nod]+costul[nod][i]);
            q.push(arc[nod][i]);
        }
    }
}

int main()
{
    f>>n>>m;
    while(m>0)
    {
        f>>x>>y>>cost;
        arc[x].push_back(y);
        costul[x].push_back(cost);
        m--;
    }
    for(i=1; i<=n ; i++)
        d[i]=2000000000;

    bfs();

    for(i=1;i<=n;i++)
        if(d[i]==2000000000)
        d[i]=0;

    for(i=1;i<n;i++)
        g<<d[i+1]<<" ";

    f.close();
    g.close();
    return 0;
}