#include <cstdio>
#include <vector>
#include <queue>
#define Nmax 50010
#define inf 999999999

using namespace std;

FILE *fin=freopen("dijkstra.in","r",stdin);
FILE *fout=freopen("dijkstra.out","w",stdout);

vector <pair <int , int> > g[Nmax];
int n,m;
int d[Nmax];
void citire()
{
    scanf("%d %d",&n,&m);
    int x,y,c;
    for(int i=0;i<m;i++)
    {
        scanf("%d %d %d",&x, &y, &c);
        g[x].push_back(make_pair(c,y));
    }
}

priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > heap;

void initial(int s)
{
   for(int i=1; i<=n;i++)
        d[i]=inf;
    heap.push(make_pair(0,s));
}

void djikstra(int s)
{
    initial(s);
    int nod, c;
    while(!heap.empty())
    {
        nod=heap.top().second;
        c=heap.top().first;
        heap.pop();
        if(d[nod]!=inf)
            continue;
        d[nod]=c;
        for( int i=0;i<g[nod].size();i++)
            heap.push(make_pair(c+g[nod][i].first,g[nod][i].second));
    }
}

void afisare()
{
    for(int i=2;i<=n;i++)
        printf("%d ",(d[i]!=inf)?d[i]:0);
}

int main()
{
    citire();
    djikstra(1);
    afisare();
    return 0;
}