#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <climits>
#define pii pair<int,int>
#define mp make_pair
#define NMAX 50005
using namespace std;

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

int n,m,dist[NMAX];
vector <pii> vecini[NMAX];
priority_queue <pii, vector<pii>, greater<pii>> pq;

void dijkstra (int start)
{
    for(int i=1;i<=n;i++)
    {
        dist[i]=INT_MAX;
    }
    dist[start]=0;
    pq.push(mp(dist[start],start));
    while(!pq.empty())
    {
        int nod=pq.top().second;
        int d=pq.top().first;
        pq.pop();
        for(auto x : vecini[nod])
        {
            if(dist[x.second]>dist[nod]+x.first && dist[nod]!=INT_MAX)
                dist[x.second]=dist[nod]+x.first;
            pq.push(mp(dist[x.second],x.second));
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        fin>>x>>y>>z;
        vecini[x].push_back(mp(z,y));
    }
    dijkstra(1);
    for(int i=2;i<=n;i++)
    {
        fout<<dist[i]<<" ";
    }
    return 0;
}