#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#define  INF 99999997
using namespace std;

priority_queue <pair<int,int> > q;
vector <pair <int,int> > G[50001];
vector <pair <int,int> > ::iterator it;
int vViz[50001],vDistante[50001];
int m,n;

void citire()
{
    int x,y,z;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        G[x].push_back(make_pair(y,z));
    }
    vDistante[1]=0;
    for(int i=2; i<=n; i++)
        vDistante[i]=INF;
}


void dijkstra()
{
    q.push(make_pair(0,1));
    int x,y;
    while(!q.empty())
    {
        x=q.top().second;
        y=q.top().first;
        q.pop();
        if((-y)!=vDistante[x]) continue;
        for(it=G[x].begin(); it!=G[x].end(); it++)
            if(vDistante[(it->first)]>(-y)+it->second)
            {
                vDistante[(it->first)]=(-y)+it->second;
                q.push(make_pair(-vDistante[(it->first)],it->first));
            }
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    dijkstra();
    for(int i=2; i<=n; i++)
        if(vDistante[i]==INF)
            printf("0 ");
        else
            printf("%d ",vDistante[i]);

    return 0;
}