#include<fstream>
#include<vector>
#include<set>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int NMAX = 50000;
const int INF = 1 << 25;

vector< int > v[NMAX+2];
vector< int > cost[NMAX+2];
set < pair <int,int> > heap;
int sol[NMAX+2],n,m;

void read()
{

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

        in>>x>>y>>c;
        v[x].push_back(y);
        cost[x].push_back(c);
    }
    in.close();
}

void djikstra()
{

    int val,nod;
    for(int i = 2 ; i <= n ; i++)
        sol[i] = INF;
    heap.insert(make_pair(0,1));
    while(heap.size()){
        val = (*heap.begin()).first;
        nod = (*heap.begin()).second;
        heap.erase(*heap.begin());
        for (int i = 0 ; i < v[nod].size() ; i++)
            if(sol[v[nod][i]] > val + cost[nod][i]){

                sol[v[nod][i]] = val + cost[nod][i];
                heap.insert(make_pair(sol[v[nod][i]],v[nod][i]));
            }
    }
}

void afis()
{

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

int main()
{

    read();
    djikstra();
    afis();
    return 0;
}