#include <cstdio>
#include <vector>
#include <queue>
#define inf 0x3f3f3f3f

using namespace std;

FILE *f=fopen("dijkstra.in","r"),*g=fopen("dijkstra.out","w");
int n,m,dist[50001],pred[50001],a,b,c;
bool in_queue[50001];
vector <pair <int,int> > u[50001];
queue <int> Q;

void citire()
{
    fscanf(f,"%i %i",&n,&m);
    for(int i=1;i<=m;i++)
    {
        fscanf(f,"%i %i %i",&a,&b,&c);
        u[a].push_back(make_pair(b,c));
    }
}

void bellmanfordfast()
{
    int x;
    for(int i=1;i<=n;i++)
        dist[i]=inf;
    dist[1]=0;
    Q.push(1);
    while(!Q.empty())
    {
        x=Q.front();
        Q.pop();
        in_queue[x]=false;
        for(int i=0;i<u[x].size();i++)
            if(dist[x]+u[x][i].second<dist[u[x][i].first])
            {
                dist[u[x][i].first]=dist[x]+u[x][i].second;
                pred[u[x][i].first]=x;
                if(!in_queue[u[x][i].first])
                {
                        Q.push(u[x][i].first);
                        in_queue[u[x][i].first]=true;
                }
            }
    }
}

int main()
{
    citire();
    bellmanfordfast();
    for(int i=2;i<=n;i++)
    {
        if(dist[i]==inf)
            fprintf(g,"0 ");
        else
            fprintf(g,"%i ",dist[i]);
    }

    return 0;
}