#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int maxn=1<<30;
int n,m;
vector <int> a[50010];
vector <int> cst[50010];
int dim[50010],solve[50010];
struct st
{
    int nod,cost;
};

bool operator < (const st & x, const st & y)
{
    return x.cost>y.cost;
}

priority_queue <st> heap;


void djk ()
{
st aux,aux2;
int nod,i;
while (!heap.empty())
{
aux=heap.top();
heap.pop();
for (i=0;i<dim[aux.nod];i++)
{
    if (solve[a[aux.nod][i]]>solve[aux.nod]+cst[aux.nod][i])
    {
        solve[a[aux.nod][i]]=solve[aux.nod]+cst[aux.nod][i];
        aux2.nod=a[aux.nod][i];
        aux2.cost=cst[aux.nod][i];
        heap.push(aux2);
    }
}
}
}

int main ()
{
f>>n>>m;
int x,i;
st aux;
for (i=1;i<=m;i++)
{
    f>>x>>aux.nod>>aux.cost;
    a[x].push_back(aux.nod);
    cst[x].push_back(aux.cost);
}
for (i=1;i<=n;i++)
    dim[i]=a[i].size();
for (i=2;i<=n;i++)
    solve[i]=maxn;
aux.nod=1;
aux.cost=0;
heap.push(aux);
djk();

for (i=2;i<=n;i++)
{
    if (solve[i]==maxn) g<<"0 ";
    else g<<solve[i]<<" ";
}

    return 0;
}