#include <fstream>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int maxn = 50001;
const int inf = 1<<30;
struct graf
{
    int nod, cost;
    graf *next;
};

int n, m;
graf *a[maxn];
int d[maxn];
bool viz[maxn];

void add(int where, int what, int cost)
{
    graf *q = new graf;
    q->nod = what;
    q->cost = cost;
    q->next = a[where];
    a[where] = q;
}
void read()
{
    f>>n>>m;
    int x, y, z;
    for ( int i = 1; i <= m; ++i )
    {
       f>>x>>y>>z;
       add(x, y, z);
    }
}
void dijkstra()
{
    for(int i=2;i<=n;i++)
        d[i]=inf;
    int mn,p=0;
    for(int i=1;i<=n;i++)
    {
        mn=inf;
        for(int j=1;j<=n;j++)
            if(d[j]<mn && viz[j]==false)
                mn=d[j],p=j;
        viz[p]=1;
        graf *t=a[p];
        while ( t )
        {
            if (d[t->nod] > d[p] + t->cost )
                d[t->nod] = d[p] + t->cost;
            t = t->next;
        }
    }
}
int main()
{
    read();
    //viz[1]=1;
  dijkstra();
  for ( int i = 2; i <= n; ++i )
    if(d[i]==inf)
    g<<"0 ";
  else
    g<<d[i]<<" ";
}