#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
ifstream intrare("bellmanford.in");
ofstream iesire("bellmanford.out");
const int NMAX=50005;
const int inf=(1<<27);
int n,m,i,j,dist[NMAX];
vector < pair < int, int > > graf[NMAX*5];
priority_queue <int, vector < int >, greater<int> > q;
bool vizitat[NMAX];

int main()
{
    intrare>>n>>m;
    int x,y,z;
    for(i=1;i<=m;i++){
        intrare>>x>>y>>z;
        graf[x].push_back(make_pair(y,z));
    }
    for(i=1;i<=n;i++)
        dist[i]=inf;

    dist[1]=0;



    for(int g=1;g<=n-1;g++){
          q.push(1);
          for(i=1;i<=n;i++)
            vizitat[i]=0;
        while(!q.empty()){
            int nod=q.top();
            vizitat[nod]=true;
            q.pop();
            for(size_t i=0;i<graf[nod].size();i++){
                int vecin=graf[nod][i].first;
                int cost=graf[nod][i].second;
                if(dist[vecin]>dist[nod]+cost){
                    dist[vecin]=dist[nod]+cost;
                    if(!vizitat[vecin])
                        q.push(vecin);
                }
            }

        }


    }





for(i=2;i<=n;i++)
    if(dist[i]==inf)
    iesire<<"0"<<" ";
else
    iesire<<dist[i]<<" ";

    return 0;
}