#include <fstream>
#include <set>
#include <vector>
#include <queue>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
#define inf   1000000000
struct edge
{
    int c,dr;
};
int Heap[50003];
vector<edge> v[50003];
int d[50003],el[50003];// pos in Heap
bool visited[50003]{false};
int heapsize = 0;
int pr(int n){return n/2;};
int ls(int n){return 2*n;};
int rs(int n ){return 2*n+1;};
void doswapH(int l, int r)
{
    swap(el[Heap[l]],el[Heap[r]]);
    swap(Heap[l],Heap[r]);

}
void pushUp(int pos, int n)
{
    while(pos != 1)
    {

        if (d[Heap[pos]]< d[Heap[pr(pos)]])
        {
            doswapH(pr(pos),pos);
            pos = pr(pos);
        }
        else
            break;
    }
}
void addH(int neu, int &n)
{
    n++;
    el[neu] = n;
    Heap[n] = neu;
    pushUp(n,n);
}

void removeMinH(int& n)
{
    doswapH(1,n);
    n--;
    int pos = 1,othpos = 1;
    while(pos <= n)
    {
        if(ls(pos)<= n && d[Heap[ls(pos)]]<d[Heap[pos]])
            othpos = ls(pos);
        if(rs(pos) <= n && d[Heap[rs(pos)]]<d[Heap[pos]])
            othpos = rs(pos);
        if(pos != othpos)
        {
            doswapH(pos,othpos);
            pos = othpos;
        }
        else
        {
            break;
        }
    }
}
void initialize(int n)
{
    for(int i = 1 ; i <= n ; i++)
    {
        d[i] = inf;
        addH(i,heapsize);
    }
}
void djkstra(int start,int n)
{
    initialize(n);
    d[start] = 0;
    int node;
    for(int i = 0 ; i <n ; i++)
    {
        node = Heap[1];
        removeMinH(heapsize);
        for(edge e :v[node])
        {
            if( d[node]+e.c < d[e.dr] )
            {
                d[e.dr] = d[node]+e.c;
                pushUp(el[e.dr],heapsize);
            }
        }
        visited[node] = true;
    }


}
int main()
{
    int a,b,c,n,m;
    in >> n >> m;
    edge e;
    for(int i = 0 ; i < m ; i++)
    {
        in >> a >> e.dr >> e.c;
        v[a].push_back(e);
    }
    djkstra(1,n);
    for(int i = 2 ; i <= n ; i++)
        out<<((d[i] == inf)?0:d[i])<<" ";
	return 0;
}