#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int MAX = 50003;
const int INF = 50000003;

priority_queue < pair<int, int>, vector< pair < int, int > >, less<pair<int, int> > >q;

vector <pair<int, int> >v[MAX];
int drum[MAX], n, m;

void dij(int sursa);

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int a, b, c;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        v[a].push_back(make_pair(c, b));
    }
    for(int i=2; i<=n; i++)
        drum[i] = INF;
    dij(1);
    for(int i=2; i<=n; i++)
        printf("%d ", drum[i]);
    return 0;
}
void dij(int sursa)
{
    int tata, cost, fiu;
    q.push(make_pair(0, sursa));
    while(!q.empty())
    {
        tata = q.top().second;
        q.pop();
        vector<pair<int, int> >::iterator it;
        for(it=v[tata].begin(); it!=v[tata].end(); ++it)
        {
            fiu = it -> second;
            cost = it -> first;
            if(drum[fiu] > drum[tata] + cost)
            {
                drum[fiu] = drum[tata] + cost;
                q.push(*it);
            }
        }
    }
}