#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#define NMAX 50001
#define INF 20001

using namespace std;

vector<int>dist;
vector<int>viz;
vector< pair<int,int> >graf[NMAX];

int nevizitat_mic(){
    int minim=INF;
    int nr;
    for(int i=1;i<(int)dist.size();i++)
        {
            if(dist[i]<minim)
                if(viz[i]==0)
                    {
                        minim = dist[i];
                        nr = i;
                    }
        }
        return nr;
}

void dijkstra(int index)
{
    for(int i=0;i<(int)graf[index].size();i++)
    {
        if(dist[index] + graf[index][i].second < dist[graf[index][i].first])
            dist[ graf[index][i].first ] = dist[index] + graf[index][i].second;
    }
    viz[index] = 1;


}

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("disjkstra.out");

    int n,m;
    int a,b,d;
    f>>n>>m;
    for(int i=0;i<m;i++){
        f>>a>>b>>d;
        graf[a].push_back(make_pair(b,d));
    }

    for(int i=0;i<=n;i++){
        dist.push_back(INF);
    }
    for(int i=0;i<=n;i++){
        viz.push_back(0);
    }

    dist[1]=0;

    for(int i=0;i<n;i++){
        dijkstra(nevizitat_mic());
    }

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


    return 0;
}