#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

struct vecin
{
    int vf, c;
};

vector<vecin> v[50001];
const int maxi=500000001;
int viz[50001], d[50001],m,n;

queue<int> q;

void bellmanford(int nod){
    int p,u,x,i,y,c;
    viz[nod]=1;
    //p=u=1;
    //q[p]=nod;
    q.push(nod);
    while(!q.empty()){
        //x=q[p++];
        x = q.front();
        q.pop();
        viz[x] = 0;
        for (unsigned i = 0; i < v[x].size(); i++)
        {
            y = v[x][i].vf;
            c = v[x][i].c;
            if (d[x] + c < d[y])
            {
                d[y] = d[x] + c;
                if (!viz[y])
                {
                    //q[++u] = y;
                    q.push(y);
                    viz[y] = 1;
                }
            }
        }
    }

}

int main()
{
    int x,y,c,i;
    vecin aux;
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y>>c;
        aux.vf = y;
        aux.c = c;
        v[x].push_back(aux);
    }
    //for(i=0;i<v[1].size();i++)
    //    d[v[1][i].vf]=v[1][i].c;
    for(i=2;i<=n;i++)
            d[i]=maxi;
    bellmanford(1);
    //int s=0;
    //for(i=2;i<=n;i++)
    //    s=s+d[i];
    //if(s>0)
    for(i=2;i<=n;i++)
            g<<d[i]<<" ";
    //else
    //    g<<"Ciclu negativ!";
    return 0;
}