#include<fstream>
#include <utility>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#define oo 20000
#define maxn 50001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int d[maxn],n,i,m;
struct sortare
{
    bool operator () (const int& a, const int &b)
    {
        return (d[a] > d[b]);
    }
};

vector <pair <int , int> > a[maxn];
//vector <pair <int , int> >::iterator j;
priority_queue < int , vector < int >, sortare > coada;

void Dijsktra(int i)
{
    int p = i;
    coada.push(i);
    d[i] = 0;
    while(!coada.empty())
    {
        p = coada.top();
        //g<<p<<'\n';
        coada.pop();
        for(int j = 0; j < a[p].size();j ++)
        if(d[a[p][j].first] > d[p] + a[p][j].second)
        {
            d[a[p][j].first] = d[p] + a[p][j].second;
            coada.push(a[p][j].first);
        }

    }
}

int main()
{
    f>>n>>m;
    int x,y,c;
    for(i = 1; i <= m; i ++)
    {
        f>>x>>y>>c;
        a[x].push_back(make_pair(y,c));
    }
    memset(d , oo, sizeof(d));
    Dijsktra(1);
    for(i = 2; i <= n; i ++)
        g<<d[i]<<'\n';
}