#include <cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

struct graf {int nod,dist; } ;

class comp{
    public:
        bool operator()(graf &A, graf &B)
        {
            if(A.dist>B.dist)
                return true;
            return false;
        }
};


priority_queue<graf, vector<graf>, comp> Q;

vector <graf> v[50001];

int d[50001],viz[50001];

int main(){

    int m,n,i,x,y,val,lim;
    graf aux;

    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&val);
        aux.nod=y;
        aux.dist=val;
        v[x].push_back(aux);
        if(x==1)
            d[y]=val;
    }

    for(i=2;i<=n;i++)
        if(v[1][i].dist==0)
            v[1][i].dist=999999999;

    aux.nod=1;
    aux.dist=0;
    Q.push(aux);
    viz[1]=1;

    while( ! Q.empty() ){

        lim=v[Q.top().nod].size();

        for(i=0;i<lim;i++){
            if( d[Q.top().nod]+v[Q.top().nod][i].dist < d[v[Q.top().nod][i].nod] )
                d[v[Q.top().nod][i].nod]=d[Q.top().nod]+v[Q.top().nod][i].dist;

            if(viz[v[Q.top().nod][i].nod]==0){
                aux.dist=d[v[Q.top().nod][i].nod];
                aux.nod=v[Q.top().nod][i].nod;
                Q.push(aux);
                viz[aux.nod]=1;
                }
            }
        Q.pop();
    }

    for(i=1;i<=n;i++)
        printf("%d ",d[i]);

    return 0;
}