#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

const int Nmax=50005;


int n,m,dist[Nmax];
vector<pair<int,int>> L[Nmax];
priority_queue<pair<int,int>> q;

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


void dijkstra()
{
    q.push({0,1});
    while(!q.empty())
    {
        int nod=q.top().second;
        int dist_nod=q.top().first;
        q.pop();
        if(dist_nod>dist[nod]) /// sa nu intre de mai multe ori
        {
            continue;       ///numai daca e convenabil
        }
        for(pair<int,int> x: L[nod])
        {
            int vec=x.first;
            if(!dist[vec] || dist[vec]>dist[nod]+x.second)
            {
                dist[vec]=dist[nod]+x.second;
                q.push({-dist[vec],vec});
            }
        }
    }
}


int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        fin>>x>>y>>z;
        L[x].push_back({y,z});
    }
    dijkstra();
    for(int i=2;i<=n;i++)
    {
        fout<<dist[i]<<" ";
    }
    return 0;
}