#include <bits/stdc++.h>

#define N_MAX 50005

using namespace std;

ifstream in("dijkstra.in");

ofstream out("dijkstra.out");

int n,m,v[N_MAX];

bool inqueue[N_MAX];

const int inf = 1<<30;

vector <pair <int, int> > lista[N_MAX];

struct compare{

    bool operator() (int d1, int d2)

    {

        return v[d1]>v[d2];

    }

};

priority_queue <int, vector<int>, compare> pq;

void dijkstra(int node)

{

    for(int i=1; i<=n; i++)

    {

        v[i]=inf;

    }

    v[node]=0;

    inqueue[node]=true;

    pq.push(node);

    while(!pq.empty())

    {

        int nod=pq.top();

        pq.pop();

        for(int i=0; i<lista[nod].size(); i++)

        {

            int vecin=lista[nod][i].first;

            int cost=lista[nod][i].second;

            if(v[nod]+cost<v[vecin])

            {

                v[vecin]=v[nod]+cost;

                if(!inqueue[vecin])

                {

                    inqueue[vecin]=true;

                    pq.push(vecin);

                }

            }

        }

    }

}

int main()

{

    in >> n >> m;

    for(int i=0; i<m; i++)

    {

        int x,y,z;

        in >> x >> y >> z;

        lista[x].push_back(make_pair(y,z));

    }

    dijkstra(1);

    for(int i=2; i<=n; i++)

    {

        if(v[i]==inf)

            out << "0 ";

        else

            out << v[i] << ' ';

    }

    return 0;

}