#include <fstream>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>


using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
int n,m;
int dmin[50005];
struct per
{
    vector <int> dest,cost;
}v[50005];

int calc()
{
    priority_queue <pair <int,int> ,vector <pair <int,int>> , greater <pair<int,int>>        > q;
    q.push({0,1});
    for(int i=1;i<=n;i++)
    {
        dmin[i]=(1<<30);
    }
    dmin[1]=0;
    while(!q.empty())
    {
        int c=q.top().first,nod=q.top().second;
        q.pop();
        for(int i=0;i<v[nod].dest.size();i++)
        {
            int aj=v[nod].dest[i],co=v[nod].cost[i];
            if(dmin[aj]>dmin[nod]+co)
            {
                dmin[aj]=dmin[nod]+co;
                q.push({dmin[aj],aj});
            }
        }

    }
    return 0;
}



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        v[a].dest.push_back(b);
        v[a].cost.push_back(c);
    }
    calc();
    for(int i=2;i<=n;i++)
    {
        cout<<dmin[i]<<" ";
    }





    return 0;
}