#include <fstream>
#include <queue>
using namespace std;


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

priority_queue< pair<int,int> >pq;

vector< pair<int,int> >v[50005];

int minn[50005];

bool ok[50005];

void dijkstra()
{
    while(!pq.empty())
    {
        pair <int,int> a = pq.top();
        pq.pop();
        if(ok[a.second]==false)
        {
            a.first=-a.first;
            ok[a.second]=true;
            for(int i=0; i<v[a.second].size(); i++)
            {
                int x=a.second;
                int y=v[a.second][i].second;
                if(ok[y]==false && minn[y]>a.first+v[x][i].first)
                {
                    minn[y]=a.first+v[x][i].first;
                    pq.push({-minn[y],y});
                }
            }
        }
    }
}

int main()
{
    pq.push({0,1});
    int n,m;
    cin>>n>>m;
    for(int i=0; i<m; i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        v[x].push_back({z,y});
    }
    for(int i=2; i<=n; i++)
        minn[i]=2100000000;
    dijkstra();
    for(int i=2; i<=n; i++)
    {
        if(minn[i]==2100000000)
            cout << 0 << " ";
        else
            cout << minn[i] << " ";
    }
}