#include <fstream>
#include <vector>
#include <utility>
#include <queue>
#define NMax 50003
#define INF 1<<28
using namespace std;
std::vector< std::pair<int,int> > G[NMax];
std::queue< std::pair<int,int> > coada;
int n,m,c,x,y,d[NMax];
void dijkstra(int x0)
{
    for(int i=1;i<=n;++i)d[i] = INF;
    d[x0] = 0;
    coada.push(std::make_pair(x0,0));
    while(!coada.empty())
    {
        int nod = (coada.front()).first;
        int val = (coada.front()).second;
        coada.pop();
        for(int i=0;i<G[nod].size();++i)
        {
            if( d[(G[nod][i]).first] > val + (G[nod][i]).second )
            {
                d[(G[nod][i]).first] = val + (G[nod][i]).second;
                coada.push(std::make_pair((G[nod][i]).first,d[(G[nod][i]).first]));
            }
        }
    }
}
int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>x>>y>>c;
        G[x].push_back(std::make_pair(y,c));
    }
    dijkstra(1);
    for(int i=2;i<=n;++i)
    {
        if(d[i] == INF)fout<<"0 ";
        else fout<<d[i]<<" ";
    }
    return 0;
}