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

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

inline void Dijsktra(int i)
{
    memset(d , oo, sizeof(d));
    int p = i;
    coada.push(i);
    d[i] = 0;
    v[i] = true;
    while(!coada.empty())
    {
        p = coada.top();
        //g<<p<<'\n';
        coada.pop();
        v[p] = false;
        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;
            if(v[a[p][j].first] == false)
            {
                coada.push(a[p][j].first);
                v[a[p][j].first] = true;
            }
        }

    }
}

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));
        //a[y].push_back(make_pair(x,c));
    }
    Dijsktra(1);
    for(i = 2; i <= n; i ++)
        g<<d[i]<<'\n';
}