#include <iostream>
#include <climits>
#include <fstream>
#include <list>
#include <vector>
#include <set>

using namespace std;
#define inf INT_MAX/2
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

void citire(list <pair <int,int> > * &L,int &n)
{
    int m;
    fin>>n>>m;
    L=new list<pair<int,int> >[n+1];
    int x,y,c;

       for(int i=0;i<m;i++)

       {fin>>x>>y>>c;
        L[x].push_back({c,y});
       }
}

void initializare(vector <int> &t,vector <int> &d, int n,int p)
{
    d.resize(n+1);
    for(int i=1;i<=n;i++)
    {
        d[i]=inf;

    }
    //actualizam distanta pana la start cu 0
    d[p]=0;

}

void Dijkstra(list <pair <int,int> > *L, int n, int st, vector <int> &t, vector <int> &d)
{
    initializare(t,d,n,st);


     int i,k;
     for(k=1;k<=n-1;k++)
     {
     for(i=1;i<=n;i++)
     {
        for(pair <int,int> pr: L[i])
        {
            int y=pr.second;
            int p=pr.first;

            if(d[y]>d[i]+p)
            {
                d[y]=d[i]+p;
            }
        }
    }
     }


    for(int i=2;i<=n;i++)
    {

            fout<<d[i]<<' ';
    }


}

int main()
{
    list <pair <int,int> > *L;
    int n,p;
    vector <int> t;
    vector <int> d;
    citire(L,n);

    Dijkstra(L,n,1,t,d);
    return 0;
}