#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#define MAX 50001
#define INF INT_MAX
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m, viz[MAX], dist[MAX], T[MAX], s[MAX];

vector < pair < int , int > > v[MAX];

queue < int > q;

void init()
    {
        for(int i=1; i<=n; i++)
            dist[i]=INF;
    }

void read()
    {
        f>>n>>m;
        int x, y, cost;
        for(int i=1; i<=m; i++)
        {
            f>>x>>y>>cost;
            v[x].push_back(make_pair(y, cost));
        }
    }

void djk()
    {
        viz[1]=1;
        init();
        q.push(1);
        dist[1]=0;
        while(!q.empty())
        {
            //cout<<"OK";
            int minn=INF;
            int node = q.front();
            q.pop();
            viz[node]=1;
            for(size_t i=0; i<v[node].size(); i++)
            {
                int extract_node = v[node][i].first;
                if(viz[extract_node]==0)
                    {
                        //cout<<node<<" "<<extract_node<<endl;
                        //cout<<dist[node]<<" "<<v[node][i].second<<" "<<dist[extract_node]<<endl;
                        if(dist[node]+v[node][i].second<dist[extract_node])
                            {
                                //cout<<"OK";
                                dist[extract_node] = dist[node]+v[node][i].second;
                                T[extract_node] = node;
                                q.push(extract_node);
                            }
                        if(dist[extract_node]<minn)
                            minn=extract_node;
                    }
            }
            /*if(minn!=INF)
                q.push(minn);*/
        }

    }

void afis()
    {
        for(int i=2; i<=n; i++)
            g<<dist[i]<<" ";
    }

int main()
{
    read();
    djk();
    afis();
    return 0;
}