#include <fstream>
#include <vector>
#include <set>
#define DIM 50010
#define INF DIM*1000
using namespace std;
vector<pair <int, int> > L[DIM];
set< pair<int, int> >S;
int V[DIM],D[DIM],i,a,b,l,n,m,k;
ifstream fin ("dijkstra.in");
ofstream fout("dijkstra.out");

int main() {
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>l;
        L[a].push_back(make_pair(b,l));
    }

    for(i=1;i<=n;i++)
        D[i]=INF;

    D[1]=0;
    S.insert(make_pair(0,1));
    while(!S.empty())
    {
        k=S.begin()->second;
        S.erase(S.begin());
        for(i=0;i<L[k].size();i++)
            if(D[L[k][i].first]>D[k]+L[k][i].second)
            {
                S.erase(make_pair(D[L[k][i].first],L[k][i].first));

                D[L[k][i].first]=D[k]+L[k][i].second;

                S.insert(make_pair(D[L[k][i].first],L[k][i].first));
            }
    }
    for(i=2;i<=n;i++)
        if(D[i]==INF)
            fout<<"0 ";
        else
            fout<<D[i]<<" ";
}