#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct Edge{
    int nod,cost;
};

int main()
{
    int N,M,i,j;
    in>>N>>M;
    vector<vector<Edge>> edge(N+1);
    set <pair<int,int>> st;
    for(i=1;i<=M;i++)
    {
        int x;
        Edge y;
        in>>x>>y.nod>>y.cost;
        edge[x].push_back(y);
    }
    int inf=(N-1)*20000;
    vector <int> d(N+1,inf);
    vector <int> viz(N+1,0);
    d[1]=0;
    st.insert({0,1});
    while(!st.empty()){
        int minim=inf+1;
        int ind;
        ind=(*st.begin()).second;
        for(auto j: edge[ind])
        {
            if(d[j.nod]>d[ind]+j.cost)
            {
                st.erase(make_pair(d[j.nod],j.nod));
                d[j.nod]=d[ind]+j.cost;
                st.insert({d[j.nod],j.nod});
            }
        }
        st.erase(st.begin());
    }
    for(i=2;i<=N;i++)
    {
        if(d[i]==inf)
            out<<"0 ";
        else
            out<<d[i]<<" ";
    }



}