#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<string.h>
#define MAXN 5005
#define INF 0x3f3f3f3f
using namespace std;

int n,m;

vector<pair<int, int> > T[MAXN];

int d[MAXN];
bool InQ[MAXN];

queue<int> q;

void read()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

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

    int i,x,y,c;
    for(i=1;i<m+1;i++)
    {
        scanf("%d %d %d",&x,&y,&c);

        T[x].push_back(make_pair(y,c));
    }
}

void dc(int z)
{


    memset (d, INF, sizeof(d));
  //  memset (InQ, false, sizeof(InQ));

    vector<pair<int,int> >::iterator it;

    d[z]=0;
    q.push(z);InQ[z]=true;
    int k;

    while(!q.empty())
    {
        k=q.front();q.pop();
        InQ[k]=false;
        for(it=T[k].begin();it!=T[k].end();it++)
        {
            if(d[k]+it->second < d[it->first])
            {
                d[it->first]=d[k]+it->second;
                if(!InQ[it->first])
                {
                    q.push(it->first);
                    InQ[it->first]=true;
                }
            }
        }
    }
}

void afis()
{
    int i;
    for(i=2;i<n+1;i++)
        if(d[i]<INF)
            printf("%d ",d[i]);
        else printf("%d",0);

}

int main()
{
    read();

    dc(1);

    afis();

    return 0;
}