#include <bits/stdc++.h>
#define oo 1<<30

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int NMAX = 50001;
vector<pair<int,int> > muchii[NMAX];
int n,m;
int best[NMAX];
queue<int> coada;
int dist[NMAX];

void citire()
{
    in>>n>>m;
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y>>z;
        muchii[x].push_back(make_pair(y,z));
    }
    in.close();
}

void bellman()
{
    for(int i=2;i<=n;i++)
        best[i]=oo;
    int target,cost;
    coada.push(1);
    while(!coada.empty())
    {
            int j = coada.front();
            for(unsigned int k=0;k<muchii[j].size();k++)
            {
                target = muchii[j][k].first;
                cost  = muchii[j][k].second;
                if(best[target] > best[j] + cost)
                {
                    best[target] = best[j] + cost;
                    coada.push(target);
                }
            }
        coada.pop();
    }
}

int main()
{
    citire();
    bellman();
    for(int i=2;i<=n;i++)
        out<<best[i]<<" ";
    out.close();
    return 0;
}