#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

#define nmax 50100

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

typedef struct muchie
{
    int a,b,cost,ord;
};
class compare
{
public:
    bool operator () (muchie a, muchie b)
    {
        return a.cost>b.cost;
    }
};
priority_queue <muchie, vector <muchie>, compare > heap;
vector <muchie> v[nmax];
bool viz[nmax*5];
int cost[nmax];

int n,m,i;

muchie x;

int main()
{
    fin>>n>>m;
    for(i=1; i<=m; ++i)
    {
        fin>>x.a>>x.b>>x.cost;
        x.ord=i;
        v[x.a].push_back(x);
    }
    cost[1]=0;

    for(i=2; i<=n; ++i)
        cost[i]=1000000000;

    for(i=0; i<v[1].size(); ++i)
    {
        viz[v[1][i].ord]=1;
        heap.push(v[1][i]);
    }

    while(heap.size())
    {
        muchie a = heap.top();
        heap.pop();
        viz[a.ord]=0;

        if(cost[a.a]+a.cost<cost[a.b])
        {
            cost[a.b]=cost[a.a]+a.cost;
            for(i=0; i<v[a.b].size(); ++i)
                if(viz[v[a.b][i].ord]==0)
                {
                    viz[v[a.b][i].ord]=1;
                    heap.push(v[a.b][i]);
                }
        }
    }
    for(i=2; i<=n; ++i)
    if(cost[i]!=1000000000)
        fout<<cost[i]<<' ';
    else
        fout<<"0 ";
}