#include<iostream>

#include<cstdio>

#include<cstring>

#include<stdio.h>

#include<string.h>

#include<cmath>

#include<math.h>

#include<algorithm>

#include<set>

#include<queue>

#include<map>

typedef long long ll;

using namespace std;

const ll mod=1e9+;

const int maxn=1e3+;

const int maxk=+;

const int maxx=1e4+;

const ll maxe=+;

#define INF 0x3f3f3f3f3f3f

int v,e;

ll cost[maxn][maxn];//cost[u][v]代表边(u,v)的权值

ll d[maxn];//从起点出发到该点的最小距离

bool vis[maxn];

void solve(int s)

{

    for(int i=;i<v;i++)

    {

        d[i]=INF;

    }

    memset(vis,false,sizeof(vis));

    d[s]=;

    while(true)

    {

        int flag=-;

        for(int i=;i<v;i++)

        {

            //在所有点中找尚未使用的最小距离的点

            if(!vis[i]&&(flag==-||d[i]<d[flag]))

            flag=i;

        }

        if(flag==-)

            break;

        vis[flag]=true;

        for(int i=;i<v;i++)

        {

            d[i]=min(d[i],d[flag]+cost[flag][i]);

        }

    }

    for(int i=;i<v;i++)

        cout<<d[i]<<" ";

    cout<<endl;

}

int main()

{

    ios::sync_with_stdio(false);

    cin>>v>>e;

    for(int i=;i<v;i++)

    {

        for(int j=;j<v;j++)

            cost[i][j]=INF;

    }

    int a,b,va;

    for(int i=;i<e;i++)

    {

        cin>>a>>b>>va;

        cost[a][b]=va;

    }

    solve();

    return ;

}