#include<fstream>
#include<vector>
#include<queue>
#define M 1<<30
#define MAXN 50001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct nod{
    int inf,c;
};
vector<nod>v[MAXN];
int cost[MAXN],n,m;
struct cmp{
    bool operator()( nod a,nod b)
    {
        if(cost[a.inf]>cost[b.inf])
            return true;
        return false;
    }
};
priority_queue<nod,vector<nod>,cmp>heap;
void citire()
{
    nod a;
    int x,y,z;
    f>>n>>m;
    for(int i=1;i<=m;i++)
        {
            f>>x>>y>>z;
            a.inf=y;
            a.c=z;
            v[x].push_back(a);
        }
}
void dijkstra()
{
    nod a;
    int nodcur,i;
    for(i=2;i<=n;i++)
        cost[i]=M;
    a.inf=1;
    a.c=0;
    heap.push(a);
    while(!heap.empty())
    {
        nodcur=heap.top().inf;
        for(i=0;i<v[nodcur].size();i++)
            {
                if(cost[v[nodcur][i].inf]>cost[nodcur]+v[nodcur][i].c)
                  {
                    cost[v[nodcur][i].inf]=cost[nodcur]+v[nodcur][i].c;
                    heap.push(v[nodcur][i]);
                  }
            }
    }
}
void afisare()
{
    for(int i=2;i<=n;i++)
        if(cost[i]==M)
            g<<0<<" ";
        else g<<cost[i]<<" ";
}
int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}