#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <fstream>
#include <cctype>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <map>
#include <bitset>
#include <stack>
/*  //c++11
#include <unordered_map>
#include <unordered_set>
#include <tuple>
*/

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector<pair<int, int> > V[50001];
set<pair<int, int> > H;
queue<int > Q;

int d1[50001];
int d2[50001];
bitset<50001> used;

void dijkstra(int root)
{
    //used[root] = true;
    H.insert(make_pair(0, root));
    d1[root] = 0;
    while(!H.empty())
    {

        int node = H.begin()->second;
        H.erase(H.begin());
        for(vector<pair<int, int> >::iterator it = V[node].begin(); it != V[node].end(); it++)
        {
            if(d1[it->second] <= it->first + d1[node])
                continue;
            set<pair<int, int> >::iterator hit = H.find(make_pair(d1[it->second],it->second));
            if(hit != H.end())
                H.erase(hit);
            d1[it->second] = it->first + d1[node];
            H.insert(make_pair(d1[it->second],it->second));
        }
    }


}

void BF(int root)
{
    used[root] = true;
    Q.push(root);
    while(!Q.empty())
    {
        int node = Q.front();
        Q.pop();
        for(vector<pair<int, int> >::iterator it = V[node].begin(); it != V[node].end(); it++)
            if(!used[it->second] || d2[it->second] > d2[node] + it->first)
            {
                used[it->second] = true;
                Q.push(it->second);
                d2[it->second] = d2[node] + it->first;
            }
    }


}

int main()
{
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    int n, m, x, y, c;
    fin>>n>>m;
    for(int i = 1; i <=m ;i ++)
    {
        fin>>x>>y>>c;
        V[x].push_back(make_pair(c,y));
    }
    for(int i = 1; i <= n; i++)
        d1[i] = 0x3f3f3f3f;
    /*dijkstra(1);
    for(int i = 2; i <= n; i++)
        fout<<d1[i]<<' ';
    fout<<'\n';*/
    BF(1);
    for(int i = 2; i <= n; i++)
        fout<<d2[i]<<' ';



    return 0;
}


//FILE!!!