#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int NMAX = 50005;
const int INF = 1<<30;
int N,M,X,Y,C,i,Dist[NMAX],L;
vector<pair<int,int> > V[NMAX];
struct PQ {int Nod,Cost;} Heap[NMAX];
void Read()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(;M;M--)
    {
        scanf("%d%d%d",&X,&Y,&C);
        V[X].push_back(make_pair(Y,C));
    }
}
void HeapUp(int F)
{
    int P=F/2;
    if(!P) return;
    if(Heap[F].Cost<Heap[P].Cost)
    {
        swap(Heap[F],Heap[P]);
        HeapUp(P);
    }
}
void HeapDown(int P)
{
    int F=P*2;
    if(F>L) return;
    if(Heap[F+1].Cost<Heap[F].Cost && F+1<=L) F=F+1;
    if(Heap[F].Cost<Heap[P].Cost)
    {
        swap(Heap[F],Heap[P]);
        HeapDown(F);
    }
}
void Delete()
{
    swap(Heap[L],Heap[1]);
    L--;
    HeapDown(1);
}
void Insert(int Nod,int Cost)
{
    Heap[++L].Nod=Nod;
    Heap[L].Cost=Cost;
    HeapUp(L);
}
void Dijkstra(int Source)
{
    for(i=1;i<=N;i++) Dist[i]=INF;
    Dist[Source]=0; Insert(Source,0);
    while(L)
    {
        int From=Heap[1].Nod; int CostFrom=Heap[1].Cost; Delete();
        if(Dist[From]<CostFrom) continue;
        for(vector<pair<int,int> >::iterator it=V[From].begin();it!=V[From].end();it++)
        {
            int Where=it->first;
            int CostWhere=it->second;
            if(Dist[From]+CostWhere<Dist[Where])
            {
                Dist[Where]=Dist[From]+CostWhere;
                Insert(Where,Dist[Where]);
            }
        }
    }
}
void Print()
{
    for(i=2;i<=N;i++)
        if(Dist[i]==INF) printf("0 ");
        else printf("%d ",Dist[i]);
}
int main()
{
    Read();
    Dijkstra(1);
    Print();
    return 0;
}