#include <fstream>
#include<queue>
#include<vector>
#define y first
#define c second
using namespace std;

int N,M, djk[50005];
vector<pair<int,int>> arce[250005];
void Dijkstra()
{
    priority_queue<pair<int,int>> pq;
    pq.push({1,0});
    while(pq.empty()==0)
    {
        int nod = pq.top().y;
        int cost= pq.top().c;
        pq.pop();
        if(cost != djk[nod])
        {
            continue;
        }
        for(size_t i=0; i < arce[nod].size(); i++)
        {
            ///ma duc prin vecini
            if(djk[arce[nod][i].y] ==0 || djk[arce[nod][i].y] > cost+ arce[nod][i].c)
            {
                djk[arce[nod][i].y]=cost+ arce[nod][i].c;
                pq.push({arce[nod][i].y, djk[arce[nod][i].y]});
            }
        }

    }
}

int main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>N>>M;
    int x,z,t;
    for(int i=1; i<=M; i++)
    {
        cin>>x>>z>>t;
        arce[x].push_back({z,t});
    }
    Dijkstra();
    for(int i=2; i<=N; i++)
    {
        cout<<djk[i]<<' ';
    }
    return 0;
}