#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
#define nmax 50001
#define inf 1001

using namespace std;
FILE *f1=fopen("dijsktra.in","r"),*f2=fopen("dijkstra.out","w");
int n,m,i,j,d;
int dist[nmax];
vector <pair <int , int> >g[nmax];
bool use[nmax];

void citire()
{
    fscanf(f1,"%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        int x,y,z;
        fscanf(f1,"%d%d%d",&x,&y,&z);
        g[x].push_back(make_pair(y,z));
    }
}
void dijkstra()
{
    for(int i=1;i<=n;i++)
    {
        for(j=0;j<g[i].size();j++)
        {

            if(dist[i]+g[i][j].second<dist[g[i][j].first])
            dist[g[i][j].first]=dist[i]+g[i][j].second;
        }
    }
}
int main()
{
    citire();
    for(int i=1;i<=n;i++)
    dist[i]=inf;
    dist[1]=0;
    dijkstra();
    for(int i=2;i<=n;i++)
        fprintf(f2,"%d ",dist[i]);
    fclose(f1);
    fclose(f2);
    return 0;
}

//Our greatest weakness lies in giving up. The most certain way to succeed is always to try just one more time.