#include <bits/stdc++.h>
using namespace std;

const int nmax = 50005;
int n, m, d[nmax];
vector< pair<int,int> > graf[nmax];
bool marked[nmax];

void apply_dijkstra()
{
    set <pair<int,int> > s;
    int tata, fiu, dist, cost, i;
    for(i=2; i<=n; i++)
        d[i]=INFINITY;
    s.insert(make_pair(0, 1));
    while(!s.empty())
    {
        tata=(*s.begin()).second;
        dist=(*s.begin()).first;
        s.erase(*s.begin());
        for(i=0; i<graf[tata].size(); i++)
        {
            fiu=graf[tata][i].first;
            cost=graf[tata][i].second;
            if(d[fiu]>cost+dist)
            {
                d[fiu]=cost+dist;
                s.insert(make_pair(d[fiu], fiu));
            }
        }
    }

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

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int x, y, c;
    scanf("%d %d",&n, &m);
    for(int i=0; i<m; i++)
    {
        scanf("%d %d %d",&x, &y, &c);
        graf[x].push_back(make_pair(y, c));
    }

    apply_dijkstra();
    fclose(stdin);
    fclose(stdout);
    return 0;
}