#include <fstream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <utility>
#include <tuple>
#define ll long long
using namespace std;
const int NMAX = 100005;
const ll INF = 1e15;
vector<tuple<int, int, int>> g[NMAX];

ll d[NMAX];
int h[NMAX], poz[NMAX], hp;
bool viz[NMAX], pushed[5 * NMAX];
vector<int> ans;

void downheap(int k){
    int nod = 1;

    while(nod)
    {
        nod = 0;

        if(k + k <= hp)
        {
            nod = k + k;
            if(nod < hp && d[h[nod]] > d[h[nod+1]]) nod ++;
            if(d[h[k]] <= d[h[nod]]) nod = 0;

            if(nod)
            {
                swap(poz[h[nod]], poz[h[k]]);
                swap(h[k], h[nod]);
                k = nod;
            }
        }
    }

}

void upheap(int k){
    while(k > 1 && d[h[k]] < d[h[k/2]]){
        swap(poz[h[k]], poz[h[k/2]]);
        swap(h[k], h[k/2]);
        k /= 2;
    }
}

bool cmp(const tuple<int,int,int> &a, const tuple<int,int,int> &b){
    return get<1>(a) < get<1>(b);
}

int main(){
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    int T,N,M,i,x,y,cost;

    //cin >> T;
    T = 1;

    while(T--)
    {
        cin >> N >> M;

        for(i=1;i<=N;++i)
        {
            d[i] = INF;
            g[i].clear();
            h[i] = i;
            poz[i] = i;
        }

        for(i=1;i<=M;++i)
        {
            cin >> x >> y >> cost;
            g[x].push_back(make_tuple(y, cost, i));
        }

        //for(i=1;i<=N;++i)
        //    sort(g[i].begin(), g[i].end());

        d[1] = 0;
        hp = N;

        while(hp){

            int best = h[1];
            swap(poz[h[1]], poz[h[hp]]);
            swap(h[1],h[hp]);
            --hp;
            downheap(1);

            for(int i=0;i<g[best].size();++i)
            {
                int to = get<0>(g[best][i]);
                int cs = get<1>(g[best][i]);
                int indx = get<2>(g[best][i]);

                if(d[to] > d[best] + cs)
                {
                    d[to] = d[best] + cs;
                    /*
                    if(!pushed[indx])
                    {
                        ans.push_back(indx);
                        pushed[indx] = 1;
                    }
                    */
                    upheap(poz[to]);
                }
            }
        }

        //for(i=1;i<=M;++i)
        //    if(!pushed[i]) ans.push_back(i);

        for(i=2;i<=N;++i)
            if(d[i] == INF) cout << "0 ";
            else cout << d[i] << ' ';
    }

    //for(i=0;i<M;++i) cout << ans[i] << ' ';



    return 0;
}