/*
//Dijkstra cu complexitate O(n^2)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
FILE *f=fopen("mat.in","r"),*g=fopen("mat.out","w");
const int inf = 2000000000;
int a,b,c,nr_vertices,nr_edges,i,j,MIN,pos_MIN,cost[50001];
vector < pair< int , int > > edge[50001];
bool vis[50001];
void select_min()
{
    MIN=inf;
    for(j=2;j<=nr_vertices;j++)
        if(vis[j]==false && MIN>cost[j])
        {
            MIN=cost[j];
            pos_MIN=j;
        }
}
void add(int vert)
{
    for(j=0;j<edge[vert].size();j++)
        if(cost[ edge[vert][j].first ] > cost[vert] + edge[vert][j].second )
            cost[ edge[vert][j].first ] = cost[vert] + edge[vert][j].second;
}
int main()
{
    fscanf(f,"%d%d",&nr_vertices,&nr_edges);
    for(i=1;i<=nr_edges;i++)
    {
        fscanf(f,"%d%d%d",&a,&b,&c);
        edge[a].push_back(make_pair(b,c));
    }
    for(i=2;i<=nr_vertices;i++)
        cost[i]=inf;
    cost[1]=0; vis[1]=true; add(1);
    for(i=1;i<=nr_vertices-2;i++)
    {
        select_min();
        vis[pos_MIN]=true;
        add(pos_MIN);
    }

    for(i=2; i <= nr_vertices ;i++)
        fprintf(g,"%d ",cost[i]);
    return 0;
}
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
FILE *f=fopen("dijkstra.in","r"),*g=fopen("dijkstra.out","w");
const int inf = 2000000000;
int a,b,c,nr_vertices,nr_edges,i,cost[50001],pos_MIN;
struct comp
{
    bool operator () (int i, int j)
    {
        return cost[i] < cost[j];
    }
};

vector < pair< int , int > > edge[50001];
priority_queue < int , vector < int > , comp > next;

void add(int vert)
{
    for(i=0;i<edge[vert].size();i++)
        if(cost[ edge[vert][i].first ] > cost[ vert ] + edge[vert][i].second)
        {
            cost[ edge[vert][i].first ] = cost[ vert ] + edge[vert][i].second;
            next.push( edge[vert][i].first );
        }
}
int main()
{
    fscanf(f,"%d%d",&nr_vertices,&nr_edges);
    for(i=1;i<=nr_edges;i++)
    {
        fscanf(f,"%d%d%d",&a,&b,&c);
        edge[a].push_back(make_pair(b,c));
    }
    for(i=2;i<=nr_vertices;i++)
        cost[i]=inf;
    cost[1]=0;  next.push(1);
    while(next.size())
    {
        pos_MIN=next.top();
        next.pop();
        add(pos_MIN);
    }
    for(i=2;i<=nr_vertices;i++)
        fprintf(g,"%d ",cost[i]);
    return 0;
}