#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <map>
#define NMAX 50002
#define INF 999999999
#define c first
#define nod second
using namespace std;

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


int n,m,grad,x,y,cost;
vector<pair<int,int> > a[NMAX];
int d[NMAX];


multimap<int,int > T;


void dijkstra()
{
    int val,x;
    for(int i=2;i<=n;i++)
        d[i] = INF;

    T.insert(make_pair(0,1));

    while(!T.empty())
    {
        val = (*T.begin()).c;
        x   = (*T.begin()).nod;

        T.erase(T.begin());

        for(int i=0;i<a[x].size();i++)
        {
            if(d[a[x][i].nod] > val + a[x][i].c)
            {
                d[a[x][i].nod] = val + a[x][i].c;

                T.insert(make_pair(d[a[x][i].nod],a[x][i].nod));

            }
        }
    }
}


int main()
{
    in >> n >> m;
    for(int i=1;i<=m;i++)
    {
        in >> x >> y >> cost;

        a[x].push_back(make_pair(cost,y));

    }
    dijkstra();
    for(int i=2;i<=n;i++)
        if(d[i]!=INF)
            out << d[i] << " ";
        else
            out << 0 << " ";

    return 0;
}