#include <fstream>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
int N, M, r[36005], contor;
set< pair<int,int> > s;
vector <int> v[36005], d[36005];
bool viz[36005];
int main()
{
    ifstream in("catun.in");
	ofstream out("catun.out");
    in >> N >> M;
    int i, a, b, c, min;
    for(i = 1; i <= N; ++i) v[i].push_back(0), d[i].push_back(0), r[i] = (1 << 30);
    r[1] = 0;
    for(i = 1; i <= M; ++i)
    {
        in >> a >> b >> c;
        v[a].push_back(b);
        v[a][0]++;
        d[a].push_back(c);
        if(c<min) min=c;
    }
    s.insert(make_pair(0,1));
    contor = 1;
    int dd, nn;
    while(contor)
    {
        dd = s.begin()->first;
        nn = s.begin()->second;
        if(viz[nn]) s.erase(s.begin()), contor--;
        else
        {
            viz[nn] = 1;
            for(i = 1; i <= v[nn][0]; ++i)
            {
                if(r[ v[nn][i] ] > r[nn] + d[nn][i] && !viz[v[nn][i]])
                {
                    r[ v[nn][i] ] = r[nn] + d[nn][i];
                    s.insert( make_pair(r[ v[nn][i] ],v[nn][i]) );
                    contor++;
                }
            }
        }
    }
    for(i = 2; i <= N; ++i)
    {
        if(r[i]< (1<<30)) out << r[i] << ' ';
        else out << "0 ";
    }
    out << '\n';
}