#include <stdio.h>
#include <vector>
#include <set>
#define N 50005
#define inf 1000000005
using namespace std;

struct arc
{
    int x,cost;
}aux;

vector<arc> g[N];
set<pair<int,int>> heap;
int n,m,i,x;
int d[N];

void afisH()
{
    for(set<pair<int,int>>::iterator it=heap.begin();it!=heap.end();it++)
        printf("%d-%d  ",it->second,it->first);
    printf("\n");
}
int main()
{
    FILE *f1,*f2;
    f1=fopen("dijkstra.in","r");
    f2=fopen("dijkstra.out","w");

    fscanf(f1,"%d%d",&n,&m);
    for(i=0;i<m;i++)
    {
        fscanf(f1,"%d%d%d",&x,&aux.x,&aux.cost);
        g[x].push_back(aux);
    }
    for(i=2;i<=n;i++)
        d[i]=inf;

    d[1]=0;
    heap.insert(make_pair(0,1));

    while(!heap.empty())
    {
        int nod=heap.begin()->second;
        heap.erase(heap.begin());

        for(i=0;i<g[nod].size();i++)
        {
            int y=g[nod][i].x;
            int cost=g[nod][i].cost;

            if(d[y]>d[nod]+cost)
            {
                if(d[y]!=inf)
                    heap.erase(heap.find(make_pair(d[y],y)));
                d[y]=d[nod]+cost;
                heap.insert(make_pair(d[y],y));
            }
        }
    }

    for(i=2;i<=n;i++)
        fprintf(f2,"%d ",d[i]);

    return 0;
}